Back to Search
Start Over
APPROXIMATING MIN-MEAN-CYCLE FOR LOW-DIAMETER GRAPHS IN NEAR-OPTIMAL TIME AND MEMORY.
- Source :
-
SIAM Journal on Optimization . 2022, Vol. 32 Issue 3, p1791-1816. 26p. - Publication Year :
- 2022
-
Abstract
- We revisit Min-Mean-Cycle, the classical problem of finding a cycle in a weighted directed graph with minimum mean weight. Despite an extensive algorithmic literature, previous work failed to achieve a near-linear runtime in the number of edges m. We propose an algorithm with near-linear runtime Õ(m(Wmax/ε)²) for computing an e additive approximation on graphs with polylogarithmic diameter and weights of magnitude at most Wmax. In particular, this is the first algorithm whose runtime scales in the number of vertices n as Õ(n²) for the complete graph. Moreover--unconditionally on the diameter--the algorithm uses only O(n) memory beyond reading the input, making it "memory-optimal". Our approach is based on solving a linear programming (LP) relaxation using entropic regularization, which reduces the LP to a Matrix Balancing problem--à la the popular reduction of Optimal Transport to Matrix Scaling. We then round the fractional LP solution using a variant of the classical Cycle-Canceling algorithm that is sped up to near-linear runtime at the expense of being approximate, and implemented in a memory-optimal manner. The algorithm is simple to implement and is competitive with the state-of-the-art methods in practice. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10526234
- Volume :
- 32
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Optimization
- Publication Type :
- Academic Journal
- Accession number :
- 159785088
- Full Text :
- https://doi.org/10.1137/21M1439390