---
_id: '1375'
abstract:
- lang: eng
  text: '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.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Sebastian
  full_name: Krinninger, Sebastian
  last_name: Krinninger
- first_name: Veronika
  full_name: Loitzenbauer, Veronika
  last_name: Loitzenbauer
- first_name: Michael
  full_name: Raskin, Michael
  last_name: Raskin
citation:
  ama: Chatterjee K, Henzinger M, Krinninger S, Loitzenbauer V, Raskin M. Approximating
    the minimum cycle mean. <i>Theoretical Computer Science</i>. 2014;547(C):104-116.
    doi:<a href="https://doi.org/10.1016/j.tcs.2014.06.031">10.1016/j.tcs.2014.06.031</a>
  apa: Chatterjee, K., Henzinger, M., Krinninger, S., Loitzenbauer, V., &#38; Raskin,
    M. (2014). Approximating the minimum cycle mean. <i>Theoretical Computer Science</i>.
    Elsevier. <a href="https://doi.org/10.1016/j.tcs.2014.06.031">https://doi.org/10.1016/j.tcs.2014.06.031</a>
  chicago: Chatterjee, Krishnendu, Monika Henzinger, Sebastian Krinninger, Veronika
    Loitzenbauer, and Michael Raskin. “Approximating the Minimum Cycle Mean.” <i>Theoretical
    Computer Science</i>. Elsevier, 2014. <a href="https://doi.org/10.1016/j.tcs.2014.06.031">https://doi.org/10.1016/j.tcs.2014.06.031</a>.
  ieee: K. Chatterjee, M. Henzinger, S. Krinninger, V. Loitzenbauer, and M. Raskin,
    “Approximating the minimum cycle mean,” <i>Theoretical Computer Science</i>, vol.
    547, no. C. Elsevier, pp. 104–116, 2014.
  ista: Chatterjee K, Henzinger M, Krinninger S, Loitzenbauer V, Raskin M. 2014. Approximating
    the minimum cycle mean. Theoretical Computer Science. 547(C), 104–116.
  mla: Chatterjee, Krishnendu, et al. “Approximating the Minimum Cycle Mean.” <i>Theoretical
    Computer Science</i>, vol. 547, no. C, Elsevier, 2014, pp. 104–16, doi:<a href="https://doi.org/10.1016/j.tcs.2014.06.031">10.1016/j.tcs.2014.06.031</a>.
  short: K. Chatterjee, M. Henzinger, S. Krinninger, V. Loitzenbauer, M. Raskin, Theoretical
    Computer Science 547 (2014) 104–116.
date_created: 2018-12-11T11:51:40Z
date_published: 2014-08-28T00:00:00Z
date_updated: 2025-09-29T13:17:21Z
day: '28'
department:
- _id: KrCh
doi: 10.1016/j.tcs.2014.06.031
ec_funded: 1
external_id:
  arxiv:
  - '1307.4473'
  isi:
  - '000340694000008'
intvolume: '       547'
isi: 1
issue: C
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1307.4473
month: '08'
oa: 1
oa_version: Preprint
page: 104 - 116
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P 23499-N23
  name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11407
  name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
  name: Microsoft Research Faculty Fellowship
publication: Theoretical Computer Science
publication_status: published
publisher: Elsevier
publist_id: '5836'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Approximating the minimum cycle mean
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 547
year: '2014'
...