Fetching the paper…
Reading the bibliography…
We revisit Min-Mean-Cycle, the classical problem of finding a cycle in a weighted directed graph with minimum mean weight.
On general minimax theorems
M. Sion · 1958
Earlier work this paper cites.
Dynamic programming and Markov processes
R. A. Howard · 1960
Earlier work this paper cites.
On pre-conditioning of matrices
E. Osborne · 1960
Earlier work this paper cites.
Optimal cycles in doubly weighted directed linear graphs
E. L. Lawler · 1966
Earlier work this paper cites.
The use of entropy maximising models, in the theory of trip distribution, mode split and route split
A. G. Wilson · 1969
Earlier work this paper cites.
Depth-first search and linear graph algorithms
R. Tarjan · 1972
Earlier work this paper cites.
A characterization of the minimum cycle mean in a digraph
R. M. Karp · 1978
Earlier work this paper cites.
On some methods for entropy maximization and matrix scaling
T. Elfving · 1980
Earlier work this paper cites.
Parametric shortest path algorithms with an application to cyclic staffing
R. M. Karp and J. B. Orlin · 1981
Earlier work this paper cites.
The complexity of dynamic languages and dynamic optimization problems
J. B. Orlin · 1981
Earlier work this paper cites.
Network flows
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin · 1988
Earlier work this paper cites.
Finding minimum-cost circulations by canceling negative cycles
A. V. Goldberg and R. E. Tarjan · 1989
Earlier work this paper cites.
Faster parametric shortest path and minimum-balance algorithms
N. E. Young, R. E. Tarjan, and J. B. Orlin · 1991
Earlier work this paper cites.
New scaling algorithms for the assignment and minimum mean cycle problems
J. B. Orlin and R. K. Ahuja · 1992
Earlier work this paper cites.
The eigenproblem in max algebra
R. Bapat, D. P. Stanford, and P. van den Driessche · 1993
Earlier work this paper cites.
Finding minimum cost to time ratio cycles with small integral transit times
M. Hartmann and J. B. Orlin · 1993
Cited alongside, same era.
Cycle times and fixed points of min-max functions
J. Gunawardena · 1994
Cited alongside, same era.
The complexity of mean payoff games on graphs
U. Zwick and M. Paterson · 1996
Cited alongside, same era.
On the complexity of matrix balancing
B. Kalantari, L. Khachiyan, and A. Shokoufandeh · 1997
Cited alongside, same era.
Numerical computation of spectral elements in max-plus algebra
J. Cochet-Terrasson, G. Cohen, S. Gaubert, M. McGettrick, and J.-P. Quadrat · 1998
Cited alongside, same era.
Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems
A. Dasdan, S. S. Irani, and R. K. Gupta · 1999
Cited alongside, same era.
LEMON–an open source C++ graph template library
B. Dezső, A. Jüttner, and P. Kovács · 2011
Later among the works it cites.
Joint spectral radius of rank one matrices and the maximum cycle mean problem
A. A. Ahmadi and P. A. Parrilo · 2012
Later among the works it cites.
Sinkhorn distances: Lightspeed computation of optimal transport
M. Cuturi · 2013
Later among the works it cites.
Approximating the minimum cycle mean
K. Chatterjee, M. Henzinger, S. Krinninger, V. Loitzenbauer, and M. A. Raskin · 2014
Later among the works it cites.
Multiplying matrices in O
V. V. Williams · 2014
Later among the works it cites.
Much faster algorithms for matrix scaling
Z. Allen-Zhu, Y. Li, R. Oliveira, and A. Wigderson · 2017
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
A minimum mean cycle cancelling method for nonlinear multicommodity flow problems
A. Ouorou and P. Mahey · 2000
Cited alongside, same era.
Inverse optimization
R. K. Ahuja and J. B. Orlin · 2001
Cited alongside, same era.
Adaptive negative cycle detection in dynamic graphs
N. Chandrachoodan, S. S. Bhattacharyya, and K. R. Liu · 2001
Cited alongside, same era.
Combinatorial optimization: polyhedra and efficiency
A. Schrijver · 2003
Cited alongside, same era.
Experimental analysis of the fastest optimum cycle ratio and mean algorithms
A. Dasdan · 2004
Cited alongside, same era.
Shortest paths in matrix multiplication time
P. Sankowski · 2005
Cited alongside, same era.
Matrix scaling and balancing via box constrained Newton’s method and interior point methods
M. B. Cohen, A. Madry, D. Tsipras, and A. Vladu · 2017
Later among the works it cites.
Matrix balancing in
R. Ostrovsky, Y. Rabani, and A. Yousefi · 2017
Later among the works it cites.
Computational optimal transport
G. Peyré and M. Cuturi · 2017
Later among the works it cites.
Approximating Min-Mean-Cycle for low-diameter graphs in near-optimal time and memory
J. M. Altschuler and P. A. Parrilo · 2020
Closest in time.
Lyapunov exponent of rank-one matrices: Ergodic formula and inapproximability of the optimal distribution
J. M. Altschuler and P. A. Parrilo · 2020
Closest in time.
Near-linear convergence of the Random Osborne algorithm for Matrix Balancing
J. M. Altschuler and P. A. Parrilo · 2020
Closest in time.
Circulation control for faster minimum cost flow in unit-capacity graphs
K. Axiotis, A. Madry, and A. Vladu · 2020
Closest in time.
Bipartite matching in nearly-linear time on moderately dense graphs
J. van den Brand, Y.-T. Lee, D. Nanongkai, R. Peng, T. Saranurak, A. Sidford, Z. Song, and D. Wang · 2020
Closest in time.
Bipartite matching in nearly-linear time on moderately dense graphs
J. van den Brand, Y.-T. Lee, D. Nanongkai, R. Peng, T. Saranurak, A. Sidford, Z. Song, and D. Wang · 2020
Closest in time.