Approximating min-mean-cycle for low-diameter graphs in near-optimal time and memory

DOI10.1137/21M1439390MaRDI QIDQ5097012zbMATH OpenOpenAlexFDO

Authors Pablo A. Parrilo, Jason M. Altschuler

Publication date 19 August 2022

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.03114

zbMATH Keywords

approximation algorithmlinear programming relaxationentropic regularizationmatrix balancingmin-mean-cyclenear-linear runtime

Mathematics Subject Classification ID

Convex programming (90C25) Programming involving graphs or networks (90C35) Approximation algorithms (68W25)

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 $m$. 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 $n$ as $ildeO(n^2)$ 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 relaxation using entropic regularization, which reduces the problem to Matrix Balancing -- 'a la the popular reduction of Optimal Transport to Matrix Scaling. The algorithm is practical and simple to implement.

Recommendations

• Approximating the minimum cycle mean
• Approximating the minimum cycle mean
• An \(O(nm)\) time algorithm for finding the min length directed cycle in a graph
• A note on finding minimum mean cycle
• scientific article; zbMATH DE number 7204576

Cites work

• scientific article; zbMATH DE number 3148886 (Why is no real title available?)
• scientific article; zbMATH DE number 744067 (Why is no real title available?)
• scientific article; zbMATH DE number 3313421 (Why is no real title available?)
• A characterization of the minimum cycle mean in a digraph
• A minimum mean cycle cancelling method for nonlinear multicommodity flow problems
• Algorithms – ESA 2005
• An experimental study of minimum mean cycle algorithms
• Approximating the minimum cycle mean
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Depth-First Search and Linear Graph Algorithms
• Engineering a combinatorial Laplacian solver: lessons learned
• Faster parametric shortest path and minimum‐balance algorithms
• Finding minimum cost to time ratio cycles with small integral transit times
• Finding minimum-cost circulations by canceling negative cycles
• Introduction to algorithms.
• Inverse Optimization
• Lyapunov Exponent of Rank-One Matrices: Ergodic Formula and Inapproximability of the Optimal Distribution
• Matrix balancing in \(L_p\) norms: bounding the convergence rate of Osborne's iteration
• Near-linear convergence of the random Osborne algorithm for matrix balancing
• Network flows. Theory, algorithms, and applications.
• New scaling algorithms for the assignment and minimum mean cycle problems
• On Pre-Conditioning of Matrices
• On general minimax theorems
• On some methods for entropy maximization and matrix scaling
• On the Complexity of Matrix Balancing
• Parametric shortest path algorithms with an application to cyclic staffing
• The complexity of mean payoff games on graphs

Cited in

(1)

• Near-linear convergence of the random Osborne algorithm for matrix balancing

This page was built for publication: Approximating min-mean-cycle for low-diameter graphs in near-optimal time and memory

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