Approximating the minimum cycle mean

Krishnendu Chatterjee
Monika Henzinger
Sebastian Krinninger
Veronika Loitzenbauer

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 + ε)-approximation algorithm for the problem and the running time of our algorithm is \tilde(O)(n^ω log^3(nW/ε) / ε), where O(n^ω) is the time required for the classic n-by-n matrix multiplication and W is the maximum value of the weights.

In Gabriele Puppis and Tiziano Villa: Proceedings Fourth International Symposium on Games, Automata, Logics and Formal Verification (GandALF 2013), Borca di Cadore, Dolomites, Italy, 29-31th August 2013, Electronic Proceedings in Theoretical Computer Science 119, pp. 136–149.
Published: 16th July 2013.

ArXived at: https://dx.doi.org/10.4204/EPTCS.119.13 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org