Approximating the minimum cycle mean
作者： Krishnendu Chatterjee , Monika Henzinger , Sebastian Krinninger , Veronika Loitzenbauer , Michael A. Raskin
DOI: 10.1016/J.TCS.2014.06.031
关键词:
摘要: We consider directed graphs where each edge is labeled with an integer weight and study the fundamental algorithmic question of computing value a cycle minimum mean weight. Our contributions are twofold: (1) First we show that reducible to problem logarithmic number min-plus matrix multiplications nxn-matrices, n vertices graph. (2) Second, when weights nonnegative, present first (1+@e)-approximation algorithm for running time our O@?(n^@wlog^3(nW/@e)/@e), O(n^@w) required classicnxn-matrix multiplication W maximum weights. With additional O(log(nW/@e)) factor in space approximately optimal can be computed within same bound.
harvard.edu
researchgate.net 
sci-hub.se 参考文章(40)
Peter Bro Miltersen, Recent Results on Howard’s Algorithm mathematical and engineering methods in computer science. pp. 53- 56 ,(2012) , 10.1007/978-3-642-36046-6_6
Chi-Him Wong, Yiu-Cheong Tam, None, Negative Cycle Detection Problem Algorithms – ESA 2005. pp. 652- 663 ,(2005) , 10.1007/11561071_58
Endre Boros, Khaled Elbassioni, Mahmoud Fouz, Vladimir Gurvich, Kazuhisa Makino, Bodo Manthey, Stochastic mean payoff games: smoothed analysis and approximation schemes international colloquium on automata languages and programming. pp. 147- 158 ,(2011) , 10.1007/978-3-642-22006-7_13
Piotr Sankowski, Shortest Paths in Matrix Multiplication Time Algorithms – ESA 2005. ,vol. 3669, pp. 770- 778 ,(2005) , 10.1007/11561071_68
Thomas Dueholm Hansen, Uri Zwick, Lower Bounds for Howard’s Algorithm for Finding Minimum Mean-Cost Cycles Algorithms and Computation. pp. 415- 426 ,(2010) , 10.1007/978-3-642-17517-6_37
Aho AV, JE Hopcroft, JD Ullman, The Design and Analysis of Computer Algorithms ,(1974)
Omid Madani, Polynomial value iteration algorithms for deterministic MDPs uncertainty in artificial intelligence. pp. 311- 318 ,(2002)
Manfred Droste, Ingmar Meinecke, Describing average- and longtime-behavior by weighted MSO logics mathematical foundations of computer science. ,vol. 6281, pp. 537- 548 ,(2010) , 10.1007/978-3-642-15155-2_47
Richard M. Karp, James B. Orlin, Parametric shortest path algorithms with an application to cyclic staffing Discrete Applied Mathematics. ,vol. 3, pp. 37- 45 ,(1981) , 10.1016/0166-218X(81)90026-3
A. Ehrenfeucht, J. Mycielski, Positional strategies for mean payoff games International Journal of Game Theory. ,vol. 8, pp. 109- 113 ,(1979) , 10.1007/BF01768705