Approximating the minimum cycle mean

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 O ˜ ( n ω log 3 ( n W / ϵ ) / ϵ ), 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 ( n W / ϵ ) ) factor in space a cycle with approximately optimal weight can be computed within the same time bound.

Authors

• Krishnendu Chatterjee Institute of Science and Technology Austria
• Monika Henzinger
• Sebastian Krinninger
• Veronika Loitzenbauer
• Michael A. Raskin

Keywords

• Quantitative verification
• Graph algorithm
• Mean-payoff objective
• Approximation algorithm