Approximating the minimum cycle mean
From MaRDI portal
Publication:2253203
DOI10.1016/J.TCS.2014.06.031zbMATH Open1417.68284arXiv1307.4473OpenAlexW2048881187MaRDI QIDQ2253203FDOQ2253203
Authors: Krishnendu Chatterjee, Sebastian Krinninger, Veronika Loitzenbauer, Michael Raskin, Monika R. Henzinger 
Publication date: 25 July 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: We consider directed graphs where each edge is labeled with an integer weight and study the fundamental algorithmic question of computing the value of a cycle with minimum mean weight. Our contributions are twofold: (1) First we show that the algorithmic question is reducible in O(n^2) time to the problem of a logarithmic number of min-plus matrix multiplications of n-by-n matrices, where n is the number of vertices of the graph. (2) Second, when the weights are nonnegative, we present the first (1 + {epsilon})-approximation algorithm for the problem and the running time of our algorithm is ilde(O)(n^omega log^3(nW/{epsilon}) / {epsilon}), where O(n^omega) is the time required for the classic n-by-n matrix multiplication and W is the maximum value of the weights.
Full work available at URL: https://arxiv.org/abs/1307.4473
Recommendations
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Approximation algorithms (68W25) Signed and weighted graphs (05C22)
Cites Work
- Network flows. Theory, algorithms, and applications.
- The complexity of mean payoff games on graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Powers of tensors and fast matrix multiplication
- Title not available (Why is that?)
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Multiplying matrices faster than coppersmith-winograd
- New scaling algorithms for the assignment and minimum mean cycle problems
- A characterization of the minimum cycle mean in a digraph
- Scaling Algorithms for the Shortest Paths Problem
- Algorithms – ESA 2005
- A linear time randomizing algorithm for searching ranked functions
- Positional strategies for mean payoff games
- Approximate binary search algorithms for mean cuts and cycles
- Cyclic games and an algorithm to find minimax cycle means in directed graphs
- On the equilibria of alternating move games
- Faster all-pairs shortest paths via circuit complexity
- New Bounds on the Complexity of the Shortest Path Problem
- On the exponent of all pairs shortest path problem
- An algorithm for finding all shortest paths using \(N^{2\cdot 81}\) infinite-precision multiplications
- More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
- Negative-cycle detection algorithms
- Faster parametric shortest path and minimum‐balance algorithms
- Parametric shortest path algorithms with an application to cyclic staffing
- Stochastic mean payoff games: smoothed analysis and approximation schemes
- Finding minimum cost to time ratio cycles with small integral transit times
- An \(O(n^ 2)\) algorithm for the maximum cycle mean of an \(n\times n\) bivalent matrix
- Describing average- and longtime-behavior by weighted MSO logics
- Lower bounds for Howard's algorithm for finding minimum mean-cost cycles
- Approximating the minimum cycle mean
- Algorithms – ESA 2005
Cited In (15)
- Computing the throughput of concatenation state machines
- Title not available (Why is that?)
- Maximum mean weight cycle in a digraph and minimizing cycle time of a logic chip
- Approximating the girth
- A note on finding minimum mean cycle
- Approximating the minimum cycle mean
- Approximating the girth
- Looking at mean-payoff and total-payoff through windows
- Minimum mean cycle problem in bidirected and skew-symmetric graphs
- Optimization of mean values on oriented graphs. Paper from the 29th Brazilian mathematics colloquium -- 29\(^{\text o}\) Colóquio Brasileiro de Matemática, Rio de Janeiro, Brazil, July 22 -- August 2, 2013
- Approximate binary search algorithms for mean cuts and cycles
- Approximating min-mean-cycle for low-diameter graphs in near-optimal time and memory
- Maximum cycle-means of weighted digraphs
- Faster algorithms for quantitative verification in bounded treewidth graphs
- Strongly polynomial-time and NC algorithms for detecting cycles in periodic graphs
This page was built for publication: Approximating the minimum cycle mean
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2253203)
