10.1016/j.tcs.2014.06.031
Chatterjee, Krishnendu
Krishnendu
Chatterjee0000-0002-4561-241X
Henzinger, Monika
Monika
Henzinger
Krinninger, Sebastian
Sebastian
Krinninger
Loitzenbauer, Veronika
Veronika
Loitzenbauer
Raskin, Michael
Michael
Raskin
Approximating the minimum cycle mean
Elsevier
2014
2018-12-11T11:51:40Z
2020-01-21T13:17:21Z
journal_article
https://research-explorer.app.ist.ac.at/record/1375
https://research-explorer.app.ist.ac.at/record/1375.json
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 to the problem of a logarithmic number of min-plus matrix multiplications of n×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 Õ(nωlog3(nW/ε)/ε),1 where O(nω) is the time required for the classic n×n-matrix multiplication and W is the maximum value of the weights. With an additional O(log(nW/ε)) factor in space a cycle with approximately optimal weight can be computed within the same time bound.