---
_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
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 MH, 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.031
apa: Chatterjee, K., Henzinger, M. H., 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.031
chicago: Chatterjee, Krishnendu, Monika H 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.
ieee: K. Chatterjee, M. H. 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.
ista: Chatterjee K, Henzinger MH, 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.” Theoretical
Computer Science, vol. 547, no. C, Elsevier, 2014, pp. 104–16, doi:10.1016/j.tcs.2014.06.031.
short: K. Chatterjee, M.H. 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: 2022-09-09T11:50:58Z
day: '28'
department:
- _id: KrCh
doi: 10.1016/j.tcs.2014.06.031
ec_funded: 1
external_id:
arxiv:
- '1307.4473'
intvolume: ' 547'
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 547
year: '2014'
...