Approximating Min-Mean-Cycle for Low-Diameter Graphs in Near-Optimal Time and Memory
From MaRDI portal
Publication:5097012
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
approximation algorithmlinear programming relaxationentropic regularizationmatrix balancingmin-mean-cyclenear-linear runtime
Programming involving graphs or networks (90C35) Convex programming (90C25) Approximation algorithms (68W25)
Related Items (1)
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 Lp 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
