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

Metadata only

Author

Haus, Utz-Uwe

Date

2014-07-24Type

- Working Paper

ETH Bibliography

yes
Altmetrics

Abstract

We call a matrix completely mixable if the entries in its columns can be permuted so that all row sums are equal. If it is not completely mixable, we want to determine the smallest maximal and largest minimal row sum attainable. These values provide a discrete approximation of of minimum variance problems for discrete distributions, a problem motivated by the question how to estimate the α -quantile of an aggregate random variable with unknown dependence structure given the marginals of the constituent random variables. We relate this problem to the multidimensional bottleneck assignment problem and show that there exists a polynomial 2 -approximation algorithm if the matrix has only 3 columns. In general, deciding complete mixability is NP -complete. In particular the swapping algorithm of Puccetti et al. is not an exact method unless NP⊆ZPP . For a fixed number of columns it remains NP -complete, but there exists a PTAS. The problem can be solved in pseudopolynomial time for a fixed number of rows, and even in polynomial time if all columns furthermore contain entries from the same multiset Show more

Publication status

publishedPages / Article No.

Publisher

Cornell UniversitySubject

Risk aggregation; VaR-bounds; Model uncertainty; Positive dependence; Bottleneck assignmentNotes

Submitted on 24 July 2014.More

Show all metadata
ETH Bibliography

yes
Altmetrics