Bounding stochastic dependence, joint mixability of matrices, and multidimensional bottleneck assignment problems

A matrix is jointly mixable if by permuting the entries in its columns all row sums can be made equal. If not jointly mixable we want to determine the smallest maximal and largest minimal row sum attainable. These values provide an approximation of the minimum variance problem for discrete distributions, estimating the αα-quantile of an aggregate random variable with unknown dependence structure. We relate this NP-hard problem to the multidimensional bottleneck assignment problem and derive a PTAS in fixed dimension.