2013/07/17 by Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger +1
Computer Science · #cs.DS
paper · pdf · doi:10.4204/eptcs.119.13
published as EPTCS 119, 2013, pp. 136-149 · In Proceedings GandALF 2013, arXiv:1307.4162
arxiv created 2013/07/17 · arxiv updated 2013/07/18
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(n2) 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 (O)(nωlog3(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.