Approximating Min-Mean-Cycle for Low-Diameter Graphs in Near-Optimal Time and Memory

DOI10.1137/21M1439390zbMath1497.90208arXiv2004.03114OpenAlexW3015540189MaRDI QIDQ5097012

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

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

Related Items (1)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On general minimax theorems
• Parametric shortest path algorithms with an application to cyclic staffing
• On some methods for entropy maximization and matrix scaling
• New scaling algorithms for the assignment and minimum mean cycle problems
• A characterization of the minimum cycle mean in a digraph
• The complexity of mean payoff games on graphs
• Engineering a combinatorial Laplacian solver: lessons learned
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A minimum mean cycle cancelling method for nonlinear multicommodity flow problems
• Approximating the minimum cycle mean
• Near-linear convergence of the random Osborne algorithm for matrix balancing
• Finding minimum cost to time ratio cycles with small integral transit times
• On Pre-Conditioning of Matrices
• Finding minimum-cost circulations by canceling negative cycles
• Inverse Optimization
• On the Complexity of Matrix Balancing
• Matrix Balancing in L_p Norms: Bounding the Convergence Rate of Osborne's Iteration
• Lyapunov Exponent of Rank-One Matrices: Ergodic Formula and Inapproximability of the Optimal Distribution
• An Experimental Study of Minimum Mean Cycle Algorithms
• Algorithms – ESA 2005
• Depth-First Search and Linear Graph Algorithms
• Faster parametric shortest path and minimum‐balance algorithms

This page was built for publication: Approximating Min-Mean-Cycle for Low-Diameter Graphs in Near-Optimal Time and Memory