Approximating Min-Mean-Cycle for low-diameter graphs in near-optimal time and memory
arXiv:2004.03114 · doi:10.1137/21M1439390
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 falls short of a near-linear runtime in the number of edges . We propose an approximation algorithm that, for graphs with polylogarithmic diameter, achieves a near-linear runtime. In particular, this is the first algorithm whose runtime scales in the number of vertices as for the complete graph. Moreover, unconditionally on the diameter, the algorithm uses only memory beyond reading the input, making it "memory-optimal". Our approach is based on solving a linear programming relaxation using entropic regularization, which reduces the problem to Matrix Balancing -- á la the popular reduction of Optimal Transport to Matrix Scaling. The algorithm is practical and simple to implement.
References in corpus (6)
- Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
- Faster Parametric Shortest Path and Minimum Balance Algorithms
- Computational Optimal Transport
- Quantitative Synthesis for Concurrent Programs
- Better Quality in Synthesis through Quantitative Objectives
- Lyapunov Exponent of Rank One Matrices: Ergodic Formula and Inapproximability of the Optimal Distribution