X. Allamigeon, P. Benchimol, and S. Gaubert, 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

]. X. Abgj13a, P. Allamigeon, S. Benchimol, M. Gaubert, and . Joswig, Combinatorial simplex algorithms can solve mean payoff games, To appear in SIAM J. on Optimization. E-print, 2013.

]. X. Abgj13b, P. Allamigeon, S. Benchimol, M. Gaubert, and . Joswig, Tropicalizing the simplex algorithm, 2013.

P. [. Allamigeon, S. Benchimol, M. Gaubert, and . Joswig, Long and winding central paths. E-print arXiv, pp.1405-4161, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01096452

[. Avis and V. Chvátal, 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

[. Avis and O. Friedmann, An exponential lower bound for Cunningham's rule. E-print arXiv:1305, 2013.

S. [. Akian, A. Gaubert, and . Guterman, 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

X. Allamigeon, S. Gaubert, and . Goubault, 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.

S. [. Allamigeon, E. Gaubert, and . Goubault, 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

S. [. Akian, A. Gaubert, and . Guterman, 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

S. [. Allamigeon, R. Gaubert, and . Katz, 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

M. Akian, S. Gaubert, V. Nitica, and I. Singer, 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

R. [. Allamigeon and . Katz, 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

R. [. Adler, R. Karp, and . Shamir, Only, Mathematics of Operations Research, vol.11, issue.4, pp.570-590, 1986.
DOI : 10.1287/moor.11.4.570

R. [. Adler, R. Karp, and . Shamir, 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

C. [. Ardila, L. Klivans, and . Williams, 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

]. D. Ale13 and . Alessandrini, Logarithmic limit sets of real semi-algebraic sets, Adv. Geometry, vol.13, issue.1, pp.155-190, 2013.

]. K. Ans91 and . Anstreicher, On the performance of Karmarkar's algorithm over a sequence of iterations, SIAM Journal on Optimization, vol.1, issue.1, pp.22-29, 1989.

G. [. Amenta and . Ziegler, Deformed products and maximal shadows of polytopes, Advances in Discrete and Computational Geometry, 1996.
DOI : 10.1090/conm/223/03132

A. [. Butkovi? and . Aminu, Introduction to max-linear programming, IMA Journal of Management Mathematics, vol.20, issue.3, pp.233-249, 2008.
DOI : 10.1093/imaman/dpn029

G. [. Baccelli, G. J. Cohen, J. Olsder, and . Quadrat, Synchronization and linearity: an algebra for discrete event systems, 1992.

. Bdse-+-12-]-n, M. D. Bonifas, F. Summa, N. Eisenbrand, M. Hähnle et al., 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.

]. G. Ber71 and . Bergman, The logarithmic limit-set of an algebraic variety. Transactions of the, pp.459-469, 1971.

G. [. Butkovi? and . Hegedüs, 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.

]. T. Bjs-+-07, A. N. Bogart, D. Jensen, B. Speyer, R. R. Sturmfels et al., 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.

]. R. Bla77 and . Bland, New finite pivoting rules for the simplex method, Mathematics of Operations Research, vol.2, issue.2, pp.103-107, 1977.

]. P. Bm14a, M. Butkovic, and . Maccaig, 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.

]. P. Bm14b, M. Butkovi?, and . Maccaig, On the integer max-linear programming problem, Discrete Applied Mathematics, vol.162, pp.128-141, 2014.

R. [. Bezem, E. Nieuwenhuis, and . Rodríguez, 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

H. [. Brunsch and . Röglin, 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

]. E. Bru12 and . Brugallé, Some aspects of tropical geometry, Newsletter of the European Mathematical Society, issue.83, pp.23-28

H. [. Butkovi?, S. Schneider, and . Sergeev, 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

]. P. But03 and . Butkovi?, Max-algebra: the linear algebra of combinatorics? Linear Algebra and its applications, pp.313-335, 2003.

]. P. But10, . [. Butkovi?, S. Bjorklund, and . Vorobyov, 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.

F. Block and J. Yu, 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

K. [. Butkovi? and . Zimmermann, 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

W. [. Charnes and . Cooper, 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

J. [. Conrad and . Dauns, 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

. [. Cuninghame-green, Minimax algebra, of Lecture Notes in Economics and Mathematical Systems, 1979.
DOI : 10.1007/978-3-642-48708-8

P. [. Cuninghame-green and . Butkovi?, 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

S. [. Cohen, J. Gaubert, and . Quadrat, 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

S. [. Cohen, J. P. Gaubert, and . Quadrat, Hahn-Banach separation theorem for max-plus semimodules, Optimal Control and Partial Differential Equations, pp.325-334, 2001.

S. [. Cohen, J. Gaubert, and . Quadrat, 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

G. Cohen, S. Gaubert, J. Quadrat, and I. Singer, 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

]. J. Cha09 and . Chaloupka, Parallel algorithms for mean-payoff games: an experimental evaluation, Algorithms?ESA, pp.599-610, 2009.

G. Cohen, P. Moller, J. Quadrat, and M. Viot, 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

]. M. Cos00 and . Coste, An introduction to o-minimal geometry, Dip. Mat. Univ. Pisa, Dottorato di Ricerca in Matematica, 2000.

S. [. Cochet-terrasson, J. Gaubert, and . Gunawardena, 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

]. G. Dan98 and . Dantzig, Linear programming and extensions. Princeton Landmarks in Mathematics, 1998.

S. [. Dhingra and . Gaubert, 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

. [. De and . Loera, New insights into the complexity and geometry of linear optimization. OPTIMA, Newsletter of the Math, Optim. Soc, vol.87, pp.1-16, 2011.

[. Loreto, S. Gaubert, R. D. Katz, and J. Loiseau, 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

E. [. De-loera, S. Kim, F. Onn, and . Santos, 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

J. De-loera, B. Sturmfels, and C. Vinzant, The central curve in linear programming. Arxiv preprint arXiv:1012, 2010.

[. Dedieu, G. Malajovich, and M. Shub, 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

E. [. Deza, R. Nematollahi, T. Peyghami, and . Terlaky, The central path visits all the vertices of the Klee?Minty cube. Optimisation Methods and Software, pp.851-865, 2006.

]. A. Dre86 and . Dress, Duality theory for finite and infinite matroids with coefficients, Adv. in Math, vol.59, issue.2, pp.97-123, 1986.

[. Dedieu and M. Shub, 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

T. [. Deza, Y. Terlaky, A. Zinchenko, T. Deza, Y. Terlaky et al., 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

W. [. Dales and . Woodin, Super-real fields. Totally ordered fields with additional structure, 1996.

J. [. Develin and . Yu, 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

M. [. Einsiedler, D. Kapranov, and . Lind, 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

J. [. Ehrenfeucht and . Mycielski, Positional strategies for mean payoff games, International Journal of Game Theory, vol.59, issue.2, pp.109-113, 1979.
DOI : 10.1007/BF01768705

U. [. Eaves and . Rothblum, 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

E. [. Filar, K. Altman, and . Avrachenkov, 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

T. [. Friedmann, U. Hansen, and . Zwick, 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

]. T. Fos10 and . Foster, Power functions and exponentials in o-minimal expansions of fields, 2010.

]. O. Fri11 and . Friedmann, 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.

. [. Frank and . Tardos, An application of simultaneous diophantine approximation in combinatorial optimization, Combinatorica, vol.4, issue.1, pp.49-65, 1987.
DOI : 10.1007/BF02579200

]. L. Fuc63 and . Fuchs, Partially ordered algebraic systems. International series of monographs in pure and applied mathematics, 1963.

C. [. Gilbert, E. Gonzaga, and . Karas, Examples of ill-behaved central paths in convex optimization, Mathematical Programming, pp.63-94, 2004.
URL : https://hal.archives-ouvertes.fr/inria-00072443

R. [. Gaubert and . Katz, 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

R. [. Gaubert and . Katz, 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

R. [. Gaubert, S. Katz, and . Sergeev, 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

L. [. Grötschel, A. Lovász, and . Schrijver, Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol.2, 1988.

M. [. Gondran and . Minoux, 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

F. [. Gaubert and . Meunier, 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

C. [. Gonçalves, L. Maia, and . Hardouin, 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

]. J. Gon12 and . Gondzio, Interior point methods 25 years later, European Journal of Operational Research, vol.218, issue.3, pp.587-601, 2012.

M. [. Gaubert and . Plus, 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

T. [. Gass and . Saaty, 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.

S. [. Gaubert and . Sergeev, 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.

]. H. Hah07 and . Hahn, ¨ Uber die nichtarchimedischen Größensysteme, Wien. Ber, vol.116, pp.601-655, 1907.

H. [. Hansen, U. Kaplan, and . Zwick, 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

]. B. Hovdw06, G. J. Heidergott, J. W. Olsder, and . Van-der-woude, 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.

G. [. Itenberg, E. Mikhalkin, and . Shustin, Tropical algebraic geometry, volume 35 of Oberwolfach Seminars, 2007.

O. [. Itenberg, . Virojer73a-]-r, and . Jeroslow, Patchworking algebraic curves disproves the ragsdale conjecture. The Mathematical Intelligencer Asymptotic linear programming, Operations Research, vol.18, issue.215, pp.19-281128, 1973.

]. R. Jer73b and . Jeroslow, The simplex algorithm with the pivot rule of maximizing criterion improvement, Discrete Mathematics, vol.4, issue.4, pp.367-377, 1973.

]. M. Jos05 and . Joswig, Tropical halfspaces, Combinatorial and computational geometry, pp.409-431, 2005.

]. M. Jos09 and . Joswig, Tropical convex hull computations, Proceedings of the International Conference on Tropical and Idempotent Mathematics, pp.193-212, 2009.

M. Jurdzi´nskijurdzi´nski, M. Paterson, and U. Zwick, A deterministic subexponential algorithm for solving parity games, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2006.

J. Albanian and . Math, E-print arXiv:0706, pp.187-211, 1918.

[. Ji and Y. Yinyu, 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

]. I. Kap42 and . Kaplansky, Maximal fields with valuations, Duke Mathematical Journal, vol.9, issue.2, pp.303-321, 1942.

]. N. Kar84 and . Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, vol.4, issue.4, pp.373-395, 1984.

]. R. Kat07 and . Katz, 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.

]. L. Kha80, . Khachiyan, . Bibliography-[-kk92-]-g, D. J. Kalai, . Kleitman-[-km72-]-v et al., 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.

]. T. Km13a, S. Kitahara, and . Mizuno, A bound for the number of different basic solutions generated by the simplex method, Mathematical Programming, vol.137, issue.12, pp.579-586, 2013.

]. T. Km13b, S. Kitahara, and . Mizuno, 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

A. [. Kakihara, T. Ohara, and . Tsuchiya, 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

D. [. Kelner and . Spielman, 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

F. [. Kim and . Santos, 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

Y. [. Kaliski and . Ye, Convergence behavior of Karmarkar's projective algorithm for solving a simple linear program. Operations research letters, pp.389-393, 1991.

]. G. Lit07 and . Litvinov, Maslov dequantization, idempotent and tropical mathematics: a brief introduction, Journal of Mathematical Sciences, vol.140, issue.3, pp.426-444, 2007.

S. [. Liggett and . Lippman, Stochastic Games with Perfect Information and Time Average Payoff, SIAM Review, vol.11, issue.4, pp.604-607, 1969.
DOI : 10.1137/1011093

V. [. Litvinov, G. B. Maslov, and . Shpiz, Idempotent Functional Analysis: An Algebraic Approach, Mar02] D. Marker. Model theory, pp.758-797, 2001.
DOI : 10.4213/mzm539

]. T. Mar10 and . Markwig, A field of generalised Puiseux series for tropical geometry, Rend. Semin. Mat., Univ. Politec. Torino, vol.68, issue.1, pp.79-92, 2010.

]. N. Meg87 and . Megiddo, On the complexity of linear programming Advances in economic theory, pp.225-268, 1987.

]. G. Mik05 and . Mikhalkin, Enumerative tropical algebraic geometry in R 2, Journal of the American Mathematical Society, vol.18, issue.2, pp.313-377, 2005.

]. C. Mil94a and . Miller, Expansions of the real field with power functions, Annals of Pure and Applied Logic, issue.93, p.72, 1994.

]. C. Mil94b and . Miller, Exponentiation is hard to avoid, Proceedings of the American Mathematical Society, p.257, 1994.

]. C. Mil12 and . Miller, Basics of o-minimality and Hardy fields, Lecture Notes on O-minimal Structures and Real Analytic Geometry, pp.43-69, 2012.

B. [. Maclagan and . Sturmfels, 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

M. [. Megiddo and . Shub, 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

T. [. Monteiro and . Tsuchiya, 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

]. M. Mt13a, T. Mut, and . Terlaky, A tight iteration-complexity upper bound for the MTY predictor-corrector algorithm via redundant Klee-Minty cubes, 2013.

]. M. Mt13b, T. Mut, and . Terlaky, An analogue of the Klee-Walkup result for Sonnevend's curvature of the central path, 2013.

]. K. Mur80 and . Murty, Computational complexity of parametric linear programming, Mathematical programming, vol.19, issue.1, pp.213-219, 1980.

]. D. Nad89 and . Naddef, The Hirsch conjecture is true for (0, 1)-polytopes, Mathematical Programming, pp.109-110, 1989.

]. J. Orl97 and . Orlin, A polynomial time primal network simplex algorithm for minimum cost flows, Mathematical Programming, pp.109-129, 1997.

]. D. Pas77 and . Passman, 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.

]. M. Pow93 and . Powell, On the number of iterations of Karmarkar's algorithm for linear programming, Mathematical Programming, vol.62, issue.1-3, pp.153-197, 1993.

]. A. Pur95 and . Puri, Theory of hybrid systems and discrete event systems, 1995.

J. Richter-gebert, B. Sturmfels, and T. Theobald, First steps in tropical geometry, Idempotent mathematics and mathematical physics, pp.289-317, 2005.
DOI : 10.1090/conm/377/06998

]. A. Rob77 and . Robinson, Complete theories, 1977.

G. [. Rahman and . Schmeisser, Analytic theory of polynomials, San12] F. Santos. A counterexample to the Hirsch conjecture, pp.383-412, 2002.

]. A. Sei54 and . Seidenberg, A new decision method for elementary algebra, Annals of Mathematics, pp.365-374, 1954.

]. I. Sin97 and . Singer, Abstract convex analysis, 1997.

]. S. Sma83 and . Smale, On the average number of steps of the simplex method of linear programming, Mathematical Programming, pp.241-262, 1983.

]. S. Sma98 and . Smale, Mathematical problems for the next century, Math. Intelligencer, vol.20, issue.2, pp.7-15, 1998.

J. [. Sonnevend, G. Stoer, and . Zhao, 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

S. [. Spielman and . Teng, Smoothed analysis of algorithms, Journal of the ACM, vol.51, issue.3, pp.385-463, 2004.
DOI : 10.1145/990308.990310

]. S. Ste10 and . Steinberg, Lattice-ordered rings and modules, 2010.

L. [. Speyer and . Williams, 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

A. [. Sturmfels and . Zelevinsky, 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

]. L. Tab13 and . Tabera, On real tropical bases and real tropical discriminants. E-print arXiv:1311, 2013.

]. A. Tar51 and . Tarski, A decision method for elementary algebra and geometry, 1951.

]. T. The06 and . Theobald, On the frontiers of polynomial computations in tropical geometry, Journal of Symbolic Computation, vol.41, issue.12, pp.1360-1375, 2006.

]. M. Tod14 and . Todd, An improved Kalai-Kleitman bound for the diameter of a polyhedron. E-print arXiv:1402, 2014.

Y. [. Todd and . Ye, 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

]. L. Val79 and . Valiant, The complexity of computing the permanent, Theoretical computer science, vol.8, issue.2, pp.189-201, 1979.

]. L. Van-den-dries and P. Speissegger, 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

]. O. Vir01 and . Viro, 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.

]. N. Zad80 and . Zadeh, 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.

M. [. Zwick and . Paterson, 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

G. Zhao and J. Stoer, 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