Near-Optimal Parallel -Matrix Scaling
En palabras de los autores
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.
Resultado principalEl resumen no menciona limitaciones.
Apareció: viernes, 16 de octubre. arXiv. Preprint, todavía sin revisión por pares.