--- 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 H foaf_name: Henzinger, Monika H foaf_surname: Henzinger foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630 orcid: 0000-0002-5008-6530 - 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@ ...