# Approximating the minimum cycle mean

Chatterjee K, Henzinger M, Krinninger S, Loitzenbauer V, Raskin M. 2014. Approximating the minimum cycle mean. Theoretical Computer Science. 547(C), 104–116.

Download (ext.)

*Journal Article*|

*Published*|

*English*

**Scopus indexed**

Author

Chatterjee, Krishnendu

^{ISTA}^{}; Henzinger, Monika; Krinninger, Sebastian; Loitzenbauer, Veronika; Raskin, MichaelDepartment

Grant

Abstract

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.

Publishing Year

Date Published

2014-08-28

Journal Title

Theoretical Computer Science

Volume

547

Issue

C

Page

104 - 116

IST-REx-ID

### Cite this

Chatterjee K, Henzinger M, Krinninger S, Loitzenbauer V, Raskin M. Approximating the minimum cycle mean.

*Theoretical Computer Science*. 2014;547(C):104-116. doi:10.1016/j.tcs.2014.06.031Chatterjee, K., Henzinger, M., Krinninger, S., Loitzenbauer, V., & Raskin, M. (2014). Approximating the minimum cycle mean.

*Theoretical Computer Science*. Elsevier. https://doi.org/10.1016/j.tcs.2014.06.031Chatterjee, Krishnendu, Monika Henzinger, Sebastian Krinninger, Veronika Loitzenbauer, and Michael Raskin. “Approximating the Minimum Cycle Mean.”

*Theoretical Computer Science*. Elsevier, 2014. https://doi.org/10.1016/j.tcs.2014.06.031.K. Chatterjee, M. Henzinger, S. Krinninger, V. Loitzenbauer, and M. Raskin, “Approximating the minimum cycle mean,”

*Theoretical Computer Science*, vol. 547, no. C. Elsevier, pp. 104–116, 2014.Chatterjee, Krishnendu, et al. “Approximating the Minimum Cycle Mean.”

*Theoretical Computer Science*, vol. 547, no. C, Elsevier, 2014, pp. 104–16, doi:10.1016/j.tcs.2014.06.031.**All files available under the following license(s):**

**Copyright Statement:**

**This Item is protected by copyright and/or related rights.**[...]

**Link(s) to Main File(s)**

Access Level

Open Access