Much faster algorithms for matrix scaling

DOI10.1109/FOCS.2017.87MaRDI QIDQ6946299zbMATH OpenFDO

Authors A. Wigderson, Zeyuan Allen Zhu, Rafael Oliveira, Yuanzhi Li

Publication date 6 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2017.87

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cited in

(9)

• Maximum flow and minimum-cost flow in almost-linear time
• Fast computation of optimal transport via entropy-regularized extragradient methods
• Fast algorithms for _p-regression
• Global Riemannian acceleration in hyperbolic and spherical spaces
• Optimization, complexity and invariant theory (invited talk)
• Almost-linear-time weighted _p-norm solvers in slightly dense graphs via sparsification
• Quantum algorithms for matrix scaling and matrix balancing
• An algorithm for reconciling indicators across multiple dimensions: weighted iterative proportional fitting
• Proportionality in multiple dimensions to design electoral systems

This page was built for publication: Much faster algorithms for matrix scaling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6946299)