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

DOI10.1137/21M1439390zbMATH Open1497.90208arXiv2004.03114OpenAlexW3015540189MaRDI QIDQ5097012FDOQ5097012

Authors: Pablo A. Parrilo, Jason M. Altschuler 

Publication date: 19 August 2022

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

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.

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

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

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)

Cites Work

• Network flows. Theory, algorithms, and applications.
• The complexity of mean payoff games on graphs
• Title not available (Why is that?)
• Introduction to algorithms.
• Depth-First Search and Linear Graph Algorithms
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On general minimax theorems
• New scaling algorithms for the assignment and minimum mean cycle problems
• A characterization of the minimum cycle mean in a digraph
• Algorithms – ESA 2005
• Finding minimum-cost circulations by canceling negative cycles
• On Pre-Conditioning of Matrices
• Inverse Optimization
• Title not available (Why is that?)
• Faster parametric shortest path and minimum‐balance algorithms
• Parametric shortest path algorithms with an application to cyclic staffing
• An experimental study of minimum mean cycle algorithms
• On some methods for entropy maximization and matrix scaling
• Near-linear convergence of the random Osborne algorithm for matrix balancing
• On the Complexity of Matrix Balancing
• Finding minimum cost to time ratio cycles with small integral transit times
• Title not available (Why is that?)
• Engineering a combinatorial Laplacian solver: lessons learned
• A minimum mean cycle cancelling method for nonlinear multicommodity flow problems
• Approximating the minimum cycle mean
• 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

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)