Approximating the minimum cycle mean

作者：Chatterjee Krishnendu; Henzinger Monika; Krinninger Sebastian; Loitzenbauer Veronika^*; Raskin Michael A

来源：Theoretical Computer Science, 2014, 547: 104-116.

DOI：10.1016/j.tcs.2014.06.031

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

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 x n-matrices, where n is the number of vertices of the graph. (2) Second, when the weights are nonnegative, we present the first (1 + is an element of)-approximation algorithm for the problem and the running time of our algorithm is (O) over tilde (n(omega) log(3) (nW/is an element of)/is an element of),(1) where O(n(omega)) is the time required for the classic n x n-matrix multiplication and W is the maximum value of the weights. With an additional O(log(nW/is an element of)) factor in space a cycle with approximately optimal weight can be computed within the same time bound.

• 出版日期2014-8-28