---
res:
bibo_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.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Chatterjee, Krishnendu
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Monika
foaf_name: Henzinger, Monika
foaf_surname: Henzinger
- foaf_Person:
foaf_givenName: Sebastian
foaf_name: Krinninger, Sebastian
foaf_surname: Krinninger
- foaf_Person:
foaf_givenName: Veronika
foaf_name: Loitzenbauer, Veronika
foaf_surname: Loitzenbauer
- foaf_Person:
foaf_givenName: Michael
foaf_name: Raskin, Michael
foaf_surname: Raskin
bibo_doi: 10.1016/j.tcs.2014.06.031
bibo_issue: C
bibo_volume: 547
dct_date: 2014^xs_gYear
dct_language: eng
dct_publisher: Elsevier@
dct_title: Approximating the minimum cycle mean@
...