The Tropical Shadow-Vertex Algorithm Solves Mean Payoff Games in Polynomial Time on Average, Automata , Languages, and Programming -41st International Colloquium, ICALP 2014 Proceedings, Part I, pp.89-100, 2014. ,
DOI : 10.1007/978-3-662-43948-7_8
URL : https://hal.archives-ouvertes.fr/hal-01096447
Combinatorial simplex algorithms can solve mean payoff games, To appear in SIAM J. on Optimization. E-print, 2013. ,
Tropicalizing the simplex algorithm, 2013. ,
Long and winding central paths. E-print arXiv, pp.1405-4161, 2014. ,
URL : https://hal.archives-ouvertes.fr/hal-01096452
Notes on Bland???s pivoting rule, Polyhedral Combinatorics, pp.24-34, 1978. ,
DOI : 10.1007/BFb0121192
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.184.816
An exponential lower bound for Cunningham's rule. E-print arXiv:1305, 2013. ,
Linear independence over tropical semirings and beyond, Proceedings of the International Conference on Tropical and Idempotent Mathematics, pp.1-38, 2009. ,
DOI : 10.1090/conm/495/09689
URL : http://arxiv.org/abs/0812.3496
The tropical double description method Tropical polyhedra are equivalent to mean payoff games, Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science of Leibniz International Proceedings in Informatics (LIPIcs) Schloss Dagstuhl? Leibniz-Zentrum fuer Informatik. 152 BIBLIOGRAPHY [AGG12] M. Akian, S. Gaubert, and A. Guterman, pp.47-58125001, 2010. ,
Computing the Vertices of Tropical Polyhedra Using Directed Hypergraphs, Discrete & Computational Geometry, vol.13, issue.2, pp.247-279 ,
DOI : 10.1007/s00454-012-9469-6
URL : https://hal.archives-ouvertes.fr/hal-00782862
Tropical Cramer determinants revisited, Proceedings of the International Conference on Tropical and Idempotent Mathematics, pp.1-45, 2014. ,
DOI : 10.1090/conm/616/12324
URL : https://hal.archives-ouvertes.fr/hal-00881203
The number of extreme points of tropical polyhedra, Journal of Combinatorial Theory, Series A, vol.118, issue.1, pp.162-189, 2011. ,
DOI : 10.1016/j.jcta.2010.04.003
Best approximation in max-plus semimodules, Linear Algebra and its Applications, vol.435, issue.12, pp.3261-3296, 2011. ,
DOI : 10.1016/j.laa.2011.06.009
Minimal external representations of tropical polyhedra, Journal of Combinatorial Theory, Series A, vol.120, issue.4, pp.907-940, 2013. ,
DOI : 10.1016/j.jcta.2013.01.011
URL : https://hal.archives-ouvertes.fr/hal-00782837
Only, Mathematics of Operations Research, vol.11, issue.4, pp.570-590, 1986. ,
DOI : 10.1287/moor.11.4.570
A simplex variant solving an m ?? d linear program in O(min(m2, d2) expected number of pivot steps, Journal of Complexity, vol.3, issue.4, pp.372-387, 1987. ,
DOI : 10.1016/0885-064X(87)90007-0
The positive Bergman complex of an oriented matroid, European Journal of Combinatorics, vol.27, issue.4, pp.577-591, 2006. ,
DOI : 10.1016/j.ejc.2004.12.006
Logarithmic limit sets of real semi-algebraic sets, Adv. Geometry, vol.13, issue.1, pp.155-190, 2013. ,
On the performance of Karmarkar's algorithm over a sequence of iterations, SIAM Journal on Optimization, vol.1, issue.1, pp.22-29, 1989. ,
Deformed products and maximal shadows of polytopes, Advances in Discrete and Computational Geometry, 1996. ,
DOI : 10.1090/conm/223/03132
Introduction to max-linear programming, IMA Journal of Management Mathematics, vol.20, issue.3, pp.233-249, 2008. ,
DOI : 10.1093/imaman/dpn029
Synchronization and linearity: an algebra for discrete event systems, 1992. ,
On sub-determinants and the diameter of polyhedra Simplet, a solver for tropical linear programming, Proceedings of the 2012 symposuim on Computational Geometry, pp.357-362, 2012. ,
The logarithmic limit-set of an algebraic variety. Transactions of the, pp.459-469, 1971. ,
An elimination method for finding all solutions of the system of linear equations over an extremal algebra, Ekonomickomatematicky Obzor, vol.20, pp.203-215, 1984. ,
Computing tropical varieties Bertsimas and X. Luo. On the worst case complexity of potential reduction algorithms for linear programming, Mathematical Programming, pp.54-73321, 1997. ,
New finite pivoting rules for the simplex method, Mathematics of Operations Research, vol.2, issue.2, pp.103-107, 1977. ,
A strongly polynomial method for solving integer max-linear optimization problems in a generic case, Journal of Optimization Theory and Applications, pp.1-23, 2014. ,
On the integer max-linear programming problem, Discrete Applied Mathematics, vol.162, pp.128-141, 2014. ,
Exponential behaviour of the Butkovi?????Zimmermann algorithm for solving two-sided linear systems in max-algebra, of Algorithms and Combinatorics, pp.3506-3509, 1987. ,
DOI : 10.1016/j.dam.2008.03.016
Finding Short Paths on Polytopes by the Shadow Vertex Algorithm, Automata, Languages, and Programming -41st International Colloquium, ICALP 2014 Proceedings, Part I, pp.279-290, 2014. ,
DOI : 10.1007/978-3-642-39206-1_24
Some aspects of tropical geometry, Newsletter of the European Mathematical Society, issue.83, pp.23-28 ,
Generators, extremals and bases of max cones, Linear Algebra and its Applications, vol.421, issue.2-3, pp.394-406, 2007. ,
DOI : 10.1016/j.laa.2006.10.004
Max-algebra: the linear algebra of combinatorics? Linear Algebra and its applications, pp.313-335, 2003. ,
Max-linear systems: theory and algorithms A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games, Discrete Appl. Math, vol.155, pp.210-229, 2007. ,
Tropical convexity via cellular resolutions, Journal of Algebraic Combinatorics, vol.9, issue.1, pp.103-114, 2006. ,
DOI : 10.1007/s10801-006-9104-9
URL : http://arxiv.org/abs/math/0503279
A strongly polynomial algorithm for solving two-sided linear systems in max-algebra, Discrete Applied Mathematics, vol.154, issue.3, pp.437-446, 2006. ,
DOI : 10.1016/j.dam.2005.09.008
THE STRONG MINKOWSKI FARKAS-WEYL THEOREM FOR VECTOR SPACES OVER ORDERED FIELDS, Proceedings of the National Academy of Sciences, vol.44, issue.9, p.914, 1958. ,
DOI : 10.1073/pnas.44.9.914
An embedding theorem for lattice-ordered fields, Pacific Journal of Mathematics, vol.30, issue.2, pp.385-398, 1969. ,
DOI : 10.2140/pjm.1969.30.385
Minimax algebra, of Lecture Notes in Economics and Mathematical Systems, 1979. ,
DOI : 10.1007/978-3-642-48708-8
The equation A???x=B???y over (max,+), Theoretical Computer Science, vol.293, issue.1, pp.3-12, 2003. ,
DOI : 10.1016/S0304-3975(02)00228-1
Max-plus algebra and system theory: Where we are and where to go now, Annual Reviews in Control, vol.23, pp.207-219, 1999. ,
DOI : 10.1016/S1367-5788(99)90091-3
Hahn-Banach separation theorem for max-plus semimodules, Optimal Control and Partial Differential Equations, pp.325-334, 2001. ,
Duality and separation theorems in idempotent semimodules, Linear Algebra and its Applications, vol.379, pp.395-422, 2004. ,
DOI : 10.1016/j.laa.2003.08.010
URL : https://hal.archives-ouvertes.fr/inria-00071917
Max-plus convex sets and functions, Idempotent Mathematics and Mathematical Physics, pp.105-129, 2005. ,
DOI : 10.1090/conm/377/06987
URL : http://arxiv.org/abs/math/0308166
Parallel algorithms for mean-payoff games: an experimental evaluation, Algorithms?ESA, pp.599-610, 2009. ,
Algebraic tools for the performance evaluation of discrete event systems, Proceedings of the IEEE, vol.77, issue.1, pp.39-85, 1989. ,
DOI : 10.1109/5.21069
An introduction to o-minimal geometry, Dip. Mat. Univ. Pisa, Dottorato di Ricerca in Matematica, 2000. ,
A constructive fixed point theorem for min-max functions, Dynamics and Stability of Systems, vol.14, issue.4, pp.407-433, 1999. ,
DOI : 10.1080/026811199281967
Linear programming and extensions. Princeton Landmarks in Mathematics, 1998. ,
How to solve large scale deterministic games with mean payoff by policy iteration, Proceedings of the 1st international conference on Performance evaluation methodolgies and tools , valuetools '06, 2006. ,
DOI : 10.1145/1190095.1190110
New insights into the complexity and geometry of linear optimization. OPTIMA, Newsletter of the Math, Optim. Soc, vol.87, pp.1-16, 2011. ,
Duality Between Invariant Spaces for Max-Plus Linear Discrete Event Systems, SIAM Journal on Control and Optimization, vol.48, issue.8, pp.485606-5628, 2010. ,
DOI : 10.1137/090747191
URL : https://hal.archives-ouvertes.fr/hal-00411243
Graphs of transportation polytopes, Journal of Combinatorial Theory, Series A, vol.116, issue.8, pp.1306-1325, 2009. ,
DOI : 10.1016/j.jcta.2009.03.010
The central curve in linear programming. Arxiv preprint arXiv:1012, 2010. ,
On the Curvature of the Central Path of Linear Programming Theory, Foundations of Computational Mathematics, vol.5, issue.2, pp.145-171, 2005. ,
DOI : 10.1007/s10208-003-0116-8
The central path visits all the vertices of the Klee?Minty cube. Optimisation Methods and Software, pp.851-865, 2006. ,
Duality theory for finite and infinite matroids with coefficients, Adv. in Math, vol.59, issue.2, pp.97-123, 1986. ,
NEWTON FLOW AND INTERIOR POINT METHODS IN LINEAR PROGRAMMING, International Journal of Bifurcation and Chaos, vol.15, issue.03, pp.827-839, 2005. ,
DOI : 10.1142/S0218127405012363
Polytopes and arrangements: Diameter and curvature, Advances in applied mathematics and global optimization, pp.215-222, 2008. ,
DOI : 10.1016/j.orl.2007.06.007
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.416.6341
Super-real fields. Totally ordered fields with additional structure, 1996. ,
Tropical Polytopes and Cellular Resolutions, Experimental Mathematics, vol.16, issue.3, pp.277-291, 2007. ,
DOI : 10.1080/10586458.2007.10129009
URL : http://arxiv.org/abs/math/0605494
Non-archimedean amoebas and tropical varieties, Journal f??r die reine und angewandte Mathematik (Crelles Journal), vol.2006, issue.601, pp.139-157, 2006. ,
DOI : 10.1515/CRELLE.2006.097
URL : http://arxiv.org/abs/math/0408311
Positional strategies for mean payoff games, International Journal of Game Theory, vol.59, issue.2, pp.109-113, 1979. ,
DOI : 10.1007/BF01768705
A Theory on Extending Algorithms for Parametric Problems, Mathematics of Operations Research, vol.14, issue.3, pp.502-533, 1989. ,
DOI : 10.1287/moor.14.3.502
An asymptotic simplex method for singularly perturbed linear programs, Operations Research Letters, vol.30, issue.5, pp.295-307, 2002. ,
DOI : 10.1016/S0167-6377(02)00152-9
Subexponential lower bounds for randomized pivoting rules for the simplex algorithm, Proceedings of the 43rd annual ACM symposium on Theory of computing, STOC '11, pp.283-292, 2011. ,
DOI : 10.1145/1993636.1993675
Power functions and exponentials in o-minimal expansions of fields, 2010. ,
A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games, Integer Programming and Combinatoral Optimization -15th International Conference, IPCO 2011. Proceedings, pp.192-206, 2011. ,
An application of simultaneous diophantine approximation in combinatorial optimization, Combinatorica, vol.4, issue.1, pp.49-65, 1987. ,
DOI : 10.1007/BF02579200
Partially ordered algebraic systems. International series of monographs in pure and applied mathematics, 1963. ,
Examples of ill-behaved central paths in convex optimization, Mathematical Programming, pp.63-94, 2004. ,
URL : https://hal.archives-ouvertes.fr/inria-00072443
The tropical analogue of polar cones, Linear Algebra and its Applications, vol.431, issue.5-7, pp.5-7608, 2009. ,
DOI : 10.1016/j.laa.2009.03.012
Minimal half-spaces and external representation of tropical polyhedra, Journal of Algebraic Combinatorics, vol.13, issue.2, pp.325-348, 2011. ,
DOI : 10.1007/s10801-010-0246-4
Tropical linear-fractional programming and parametric mean payoff games, Journal of Symbolic Computation, vol.47, issue.12, pp.471447-1478, 2012. ,
DOI : 10.1016/j.jsc.2011.12.049
URL : https://hal.archives-ouvertes.fr/hal-00782737
Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol.2, 1988. ,
Linear Algebra in Dioids: A Survey of Recent Results, Annals of Discrete Mathematics, vol.19, pp.147-164, 1984. ,
DOI : 10.1016/S0304-0208(08)72960-8
Carath??odory, Helly and the Others in the Max-Plus World, Discrete & Computational Geometry, vol.13, issue.2, pp.648-662, 2010. ,
DOI : 10.1007/s00454-009-9207-x
On tropical fractional linear programming, Gol94] D. Goldfarb. On the complexity of the simplex method Advances in optimization and numerical analysis, pp.384-396, 1994. ,
DOI : 10.1016/j.laa.2014.07.002
Interior point methods 25 years later, European Journal of Operational Research, vol.218, issue.3, pp.587-601, 2012. ,
Methods and applications of (max,+) linear algebra, Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science, Lybeck, Germany February 17, pp.261-282, 1997. ,
DOI : 10.1007/BFb0023465
URL : https://hal.archives-ouvertes.fr/inria-00073603
The computational algorithm for the parametric objective function Naval research logistics quarterly, GS79] D. Goldfarb and W. Y. Sit. Worst case behavior of the steepest edge simplex method, pp.39-45277, 1955. ,
Cyclic projectors and separation theorems in idempotent convex geometry. Fundamentalnaya i prikladnaya matematika, Engl. translation in Journal of Mathematical Sciences, vol.13, issue.155 6, pp.33-52815, 2007. ,
¨ Uber die nichtarchimedischen Größensysteme, Wien. Ber, vol.116, pp.601-655, 1907. ,
Dantzig's pivoting rule for shortest paths, deterministic MDPs, and minimum cost to time ratio cycles, SODA, pp.847-860, 2014. ,
DOI : 10.1137/1.9781611973402.63
Max Plus at work: modeling and analysis of synchronized systems: a course on Max-Plus algebra and its applications, IKS03] I. Itenberg, V. Kharlamov, and E. Shustin. Welschinger invariant and enumeration of real rational curves. International Mathematics research notices, pp.20032639-2653, 2003. ,
Tropical algebraic geometry, volume 35 of Oberwolfach Seminars, 2007. ,
Patchworking algebraic curves disproves the ragsdale conjecture. The Mathematical Intelligencer Asymptotic linear programming, Operations Research, vol.18, issue.215, pp.19-281128, 1973. ,
The simplex algorithm with the pivot rule of maximizing criterion improvement, Discrete Mathematics, vol.4, issue.4, pp.367-377, 1973. ,
Tropical halfspaces, Combinatorial and computational geometry, pp.409-431, 2005. ,
Tropical convex hull computations, Proceedings of the International Conference on Tropical and Idempotent Mathematics, pp.193-212, 2009. ,
A deterministic subexponential algorithm for solving parity games, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2006. ,
E-print arXiv:0706, pp.187-211, 1918. ,
A Complexity Analysis for Interior-Point Algorithms Based on Karmarkar???s Potential Function, SIAM Journal on Optimization, vol.4, issue.3, pp.512-520, 1994. ,
DOI : 10.1137/0804028
Maximal fields with valuations, Duke Mathematical Journal, vol.9, issue.2, pp.303-321, 1942. ,
A new polynomial-time algorithm for linear programming, Combinatorica, vol.4, issue.4, pp.373-395, 1984. ,
Max-plus (A, B)-invariant spaces and control of timed discrete event systems, IEEE Trans. Aut. Control, vol.52, issue.2, pp.229-241, 2007. ,
Polynomial algorithms in linear programming A quasi-polynomial bound for the diameter of graphs of polyhedra How good is the simplex method?, Inequalities III (Proceedings of the Third Symposium on Inequalities held at the University of California, pp.53-72315, 1969. ,
A bound for the number of different basic solutions generated by the simplex method, Mathematical Programming, vol.137, issue.12, pp.579-586, 2013. ,
An upper bound for the number of different solutions generated by the primal simplex method with any selection rule of entering variables, Asia-Pacific Journal of Operational Research, issue.03, pp.30-2013 ,
Information Geometry and Interior-Point Algorithms in Semidefinite Programs and Symmetric Cone Programs, Journal of Optimization Theory and Applications, vol.74, issue.1, Ser.??A, pp.749-780, 2013. ,
DOI : 10.1007/s10957-012-0180-9
A randomized polynomial-time simplex algorithm for linear programming, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing , STOC '06, pp.51-60, 2006. ,
DOI : 10.1145/1132516.1132524
An Update on the Hirsch Conjecture, Jahresbericht der Deutschen Mathematiker-Vereinigung, vol.112, issue.2, pp.73-98, 2010. ,
DOI : 10.1365/s13291-010-0001-8
Convergence behavior of Karmarkar's projective algorithm for solving a simple linear program. Operations research letters, pp.389-393, 1991. ,
Maslov dequantization, idempotent and tropical mathematics: a brief introduction, Journal of Mathematical Sciences, vol.140, issue.3, pp.426-444, 2007. ,
Stochastic Games with Perfect Information and Time Average Payoff, SIAM Review, vol.11, issue.4, pp.604-607, 1969. ,
DOI : 10.1137/1011093
Idempotent Functional Analysis: An Algebraic Approach, Mar02] D. Marker. Model theory, pp.758-797, 2001. ,
DOI : 10.4213/mzm539
A field of generalised Puiseux series for tropical geometry, Rend. Semin. Mat., Univ. Politec. Torino, vol.68, issue.1, pp.79-92, 2010. ,
On the complexity of linear programming Advances in economic theory, pp.225-268, 1987. ,
Enumerative tropical algebraic geometry in R 2, Journal of the American Mathematical Society, vol.18, issue.2, pp.313-377, 2005. ,
Expansions of the real field with power functions, Annals of Pure and Applied Logic, issue.93, p.72, 1994. ,
Exponentiation is hard to avoid, Proceedings of the American Mathematical Society, p.257, 1994. ,
Basics of o-minimality and Hardy fields, Lecture Notes on O-minimal Structures and Real Analytic Geometry, pp.43-69, 2012. ,
Introduction to tropical geometry. Draft of a book ,
DOI : 10.1090/gsm/161
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.190.4769
Boundary Behavior of Interior Point Algorithms in Linear Programming, Mathematics of Operations Research, vol.14, issue.1, pp.97-146, 1989. ,
DOI : 10.1287/moor.14.1.97
A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms, Mathematical Programming, pp.105-149, 2008. ,
DOI : 10.1007/s10107-007-0141-5
A tight iteration-complexity upper bound for the MTY predictor-corrector algorithm via redundant Klee-Minty cubes, 2013. ,
An analogue of the Klee-Walkup result for Sonnevend's curvature of the central path, 2013. ,
Computational complexity of parametric linear programming, Mathematical programming, vol.19, issue.1, pp.213-219, 1980. ,
The Hirsch conjecture is true for (0, 1)-polytopes, Mathematical Programming, pp.109-110, 1989. ,
A polynomial time primal network simplex algorithm for minimum cost flows, Mathematical Programming, pp.109-129, 1997. ,
The algebraic structure of group rings BIBLIOGRAPHY [Plu90] M. Plus. Linear systems in (max,+) algebra, Proceedings of the 29th IEEE Conference on Decision and ControlPoo93] B. Poonen. Maximally complete fields, pp.151-15687, 1977. ,
On the number of iterations of Karmarkar's algorithm for linear programming, Mathematical Programming, vol.62, issue.1-3, pp.153-197, 1993. ,
Theory of hybrid systems and discrete event systems, 1995. ,
First steps in tropical geometry, Idempotent mathematics and mathematical physics, pp.289-317, 2005. ,
DOI : 10.1090/conm/377/06998
Complete theories, 1977. ,
Analytic theory of polynomials, San12] F. Santos. A counterexample to the Hirsch conjecture, pp.383-412, 2002. ,
A new decision method for elementary algebra, Annals of Mathematics, pp.365-374, 1954. ,
Abstract convex analysis, 1997. ,
On the average number of steps of the simplex method of linear programming, Mathematical Programming, pp.241-262, 1983. ,
Mathematical problems for the next century, Math. Intelligencer, vol.20, issue.2, pp.7-15, 1998. ,
On the complexity of following the central path of linear programs by linear extrapolation II, Mathematical Programming, pp.1-3527, 1991. ,
DOI : 10.1007/BF01582904
Smoothed analysis of algorithms, Journal of the ACM, vol.51, issue.3, pp.385-463, 2004. ,
DOI : 10.1145/990308.990310
Lattice-ordered rings and modules, 2010. ,
The Tropical Totally Positive Grassmannian, Journal of Algebraic Combinatorics, vol.190, issue.1/2, pp.189-210, 2005. ,
DOI : 10.1007/s10801-005-2513-3
Maximal Minors and Their Leading Terms, Advances in Mathematics, vol.98, issue.1, pp.65-112, 1993. ,
DOI : 10.1006/aima.1993.1013
URL : http://doi.org/10.1006/aima.1993.1013
On real tropical bases and real tropical discriminants. E-print arXiv:1311, 2013. ,
A decision method for elementary algebra and geometry, 1951. ,
On the frontiers of polynomial computations in tropical geometry, Journal of Symbolic Computation, vol.41, issue.12, pp.1360-1375, 2006. ,
An improved Kalai-Kleitman bound for the diameter of a polyhedron. E-print arXiv:1402, 2014. ,
A lower bound on the number of iterations of long-step primal-dual linear programming algorithms, Annals of Operations Research, vol.19, issue.1, pp.233-252, 1996. ,
DOI : 10.1007/BF02206818
The complexity of computing the permanent, Theoretical computer science, vol.8, issue.2, pp.189-201, 1979. ,
The real field with convergent generalized power series, Vin12] C. Vinzant. Real radical initial ideals, pp.4377-4421392, 1998. ,
DOI : 10.1090/S0002-9947-98-02105-9
Dequantization of real algebraic geometry on logarithmic paper [VY96] S. Vavasis and Y. Ye. A primal-dual interior point method whose running time depends only on the constraint matrix BIBLIOGRAPHY [Wri05] M. Wright. The interior-point revolution in optimization: history, recent developments, and lasting consequences, European Congress of Mathematics Mathematical Programming, pp.135-14679, 1996. ,
What is the worst case behavior of the simplex algorithm? A general separation theorem in extremal algebras, Departement of Operations Research Ekonom.-Mat. Obzor, vol.13, issue.2, pp.179-201, 1977. ,
The complexity of mean payoff games on graphs, Theoretical Computer Science, vol.158, issue.1-2, pp.343-359, 1996. ,
DOI : 10.1016/0304-3975(95)00188-3
Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals, Applied Mathematics & Optimization, vol.62, issue.1, pp.85-103, 1993. ,
DOI : 10.1007/BF01182599