Abstract:
We study the problem of permuting each column of a given matrix to achieve minimum maximal row sum or maximum minimal row sum, a problem of interest in quantitative finance where quantiles of a random variable expressed as the sum of several random variables with unknown dependence structure are estimated. If the minimum maximal row sum is equal to maximum minimal row sum the matrix is termed {\it jointly mixable}. We show that the lack of joint mixability (the joint mixability gap) is not significant, i.e., the gap between minimum maximal row sum and the maximum minimum row sum is either zero or one for a class of integral matrices including binary and complete consecutive integers matrices. For integer matrices where all entries are drawn from a given set of discrete values, we show that the gap can be as large as the difference between the maximal and minimal elements of the discrete set. The aforementioned result also leads to a Polynomial-Time Approximation Scheme for matrices with restricted domain. Computing the gap for a $\{0,1,2\}$-matrix is proved to be equivalent to finding column permutations minimizing the difference between the maximum and minimum row sums. A polynomial procedure for computing the optimum difference by solving the maximum flow problem on an appropriate graph is given. Keywords: Jointly mixable matrices, Quantiles, PTAS. AMS subject classifications: 05B20, 15B36, 11C20, 60C05, 90C47, 90C59