Approximating the minimum cycle mean
From MaRDI portal
Publication:2253203
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3643026 (Why is no real title available?)
- scientific article; zbMATH DE number 3148886 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- A characterization of the minimum cycle mean in a digraph
- A linear time randomizing algorithm for searching ranked functions
- Algorithms – ESA 2005
- Algorithms – ESA 2005
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- An O(n^ 2) algorithm for the maximum cycle mean of an n n bivalent matrix
- An algorithm for finding all shortest paths using \(N^{2\cdot 81}\) infinite-precision multiplications
- Approximate binary search algorithms for mean cuts and cycles
- Approximating the minimum cycle mean
- Cyclic games and an algorithm to find minimax cycle means in directed graphs
- Describing average- and longtime-behavior by weighted MSO logics
- Faster all-pairs shortest paths via circuit complexity
- Faster parametric shortest path and minimum‐balance algorithms
- Finding minimum cost to time ratio cycles with small integral transit times
- Lower bounds for Howard's algorithm for finding minimum mean-cost cycles
- More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
- Multiplying matrices faster than coppersmith-winograd
- Negative-cycle detection algorithms
- Network flows. Theory, algorithms, and applications.
- New Bounds on the Complexity of the Shortest Path Problem
- New scaling algorithms for the assignment and minimum mean cycle problems
- On the equilibria of alternating move games
- On the exponent of all pairs shortest path problem
- Parametric shortest path algorithms with an application to cyclic staffing
- Positional strategies for mean payoff games
- Powers of tensors and fast matrix multiplication
- Scaling Algorithms for the Shortest Paths Problem
- Stochastic mean payoff games: smoothed analysis and approximation schemes
- The complexity of mean payoff games on graphs
Cited in
(15)- Computing the throughput of concatenation state machines
- scientific article; zbMATH DE number 5291597 (Why is no real title available?)
- 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
- Looking at mean-payoff and total-payoff through windows
- Approximating the minimum cycle mean
- Approximating the girth
- 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)
