Finding Hall Blockers by Matrix Scaling

References

• [1] Aas E (2014) Limit points of the iterative scaling procedure. Ann. Oper. Res. 215(1):15–23.Crossref, Google Scholar
• [2] Altschuler JM, Weed J, Rigollet P (2017) Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. Guyon S, von Luxburg U, Bengio S, Wallach HM, Fergus R, Vishwanathan SVN, Garnett R, eds. Adv. Neural Inform. Processing Systems, Annual Conference on Neural Information Processing Systems, vol. 30, 1964–1974.Google Scholar
• [3] Beck A (2017) First-Order Methods in Optimization (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [4] Boyd S, Kim S-J, Vandenberghe L, Hassibi A (2007) A tutorial on geometric programming. Optim. Engrg. 8(1):67–127.Crossref, Google Scholar
• [5] Bregman LM (1967) The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Comput. Math. Math. Phys. 7(3):200–217.Crossref, Google Scholar
• [6] Bürgisser P, Li Y, Nieuwboer H, Walter M (2020) Interior-point methods for unconstrained geometric programming and scaling problems. Preprint, submitted August 27, https://arxiv.org/abs/2008.12110.Google Scholar
• [7] Chakrabarty D, Khanna S (2021) Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling. Math. Programming 188(1):395–407.Crossref, Google Scholar
• [8] Cover TM, Thomas JA (2006) Elements of Information Theory, 2nd ed. (Wiley-Interscience, Hoboken, NJ).Google Scholar
• [9] Csiszár I (1975) I-divergence geometry of probability distributions and minimization problems. Ann. Probab. 3(1):146–158.Crossref, Google Scholar
• [10] Csiszár I, Tusnády G (1984) Information geometry and alternating minimization procedures. Statist. Decisions 1(Suppl 1):205–237.Google Scholar
• [11] Dulmage AL, Mendelsohn NS (1958) Coverings of bipartite graphs. Canadian J. Math. 10:517–534.Crossref, Google Scholar
• [12] Franks C (2018) Operator scaling with specified marginals. Diakonikolas I, Kempe D, Henzinger M, eds. STOC’18—Proc. 50th Annual ACM SIGACT Sympos. Theory Comput. (ACM, New York), 190–203.Google Scholar
• [13] Franks C, Soma T, Goemans MX (2023) Shrunk subspaces via operator Sinkhorn iteration. Bansal N, Nagarajan V, eds. Proc. 2023 Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 1655–1668.Google Scholar
• [14] Fujishige S (2005) Submodular Functions and Optimization, 2nd ed. (Elsevier B.V., Amsterdam).Google Scholar
• [15] Fujishige S (2009) Theory of principal partitions revisited. Cook W, Lovász L, Vygen J, eds. Research Trends in Combinatorial Optimization (Springer, Berlin), 127–162.Crossref, Google Scholar
• [16] Gallo G, Grigoriadis MD, Tarjan RE (1989) A fast parametric maximum flow algorithm and applications. SIAM J. Comput. 18(1):30–55.Crossref, Google Scholar
• [17] Garg A, Oliveira R (2018) Recent progress on scaling algorithms and applications. Bull. Eur. Assoc. Theoret. Comput. Sci. 125:14–49.Google Scholar
• [18] Garg A, Gurvits L, Oliveira R, Wigderson A (2020) Operator scaling: Theory and applications. Foundations Comput. Math. 20(2):223–290.Crossref, Google Scholar
• [19] Gietl C, Reffel FP (2013) Accumulation points of the iterative proportional fitting procedure. Metrika 76(6):783–798.Crossref, Google Scholar
• [20] Gurvits L (2004) Classical complexity and quantum entanglement. J. Comput. System Sci. 69(3):448–484.Crossref, Google Scholar
• [21] Gurvits L, Yianilos PN (1998) The deflation-inflation method for certain semidefinite programming and maximum determinant completion problems. Technical report, NEC Research Institute, Princeton, NJ.Google Scholar
• [22] Idel M (2016) A review of matrix scaling and Sinkhorn’s normal form for matrices and positive maps. Preprint, submitted September 20, https://arxiv.org/abs/1609.06349.Google Scholar
• [23] Linial N, Samorodnitsky A, Wigderson A (2000) A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. Combinatorica 20(4):545–568.Crossref, Google Scholar
• [24] Lovász L, Plummer MD (1986) Matching Theory (North-Holland Publishing Co., Amsterdam).Google Scholar
• [25] Matsuda T, Soma T (2022) Information geometry of operator scaling. Linear Algebra Appl. 649:240–267.Crossref, Google Scholar
• [26] Murota K (2000) Matrices and Matroids for Systems Analysis (Springer-Verlag, Berlin).Google Scholar
• [27] Rothblum UG, Schneider H (1989) Scalings of matrices which have prespecified row sums and column sums via optimization. Linear Algebra Appl. 114/115:737–764.Crossref, Google Scholar
• [28] Sinkhorn R (1964) A relationship between arbitrary positive matrices and doubly stochastic matrices. Ann. Math. Statist. 35(2):876–879.Crossref, Google Scholar
• [29] Sinkhorn R, Knopp P (1967) Concerning nonnegative matrices and doubly stochastic matrices. Pacific J. Math. 21(2):343–348.Crossref, Google Scholar
• [30] Tomizawa N, Fujishige S (1982) Historical survey of extension of the concept of principal partition and their unifying generalization of hypermatroids. System Science Research Report No. 5, Department of Systems Science, Graduate School of Science and Engineering, Tokyo Institute of Technology, Tokyo.Google Scholar