pipette
ESEspañol

Near-Optimal Parallel -Matrix Scaling

Chih-Hung Liu, Aaron Sidford, Ta-Wei Tu

Preprint

In the authors' words

In this paper we consider the problem of computing a positive diagonal scaling of a symmetric -matrix so that all row and column sums are . We provide a poly-logarithmic iteration algorithm that solves this problem to high accuracy, where the cost of each iteration is dominated by the cost of solving a Laplacian system. This improves upon the recent iteration bound of [Vladu STOC 2025] and yields a randomized algorithm for the problem that runs in near-linear time and poly-logarithmic parallel depth.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 16. arXiv. Preprint, not yet peer-reviewed.