×

Abstract tropical linear programming. (English) Zbl 1454.14157

Summary: In this paper we develop a combinatorial abstraction of tropical linear programming. This generalizes the search for a feasible point of a system of min-plus-inequalities. We obtain an algorithm based on an axiomatic approach to this generalization. It builds on the introduction of signed tropical matroids based on the polyhedral properties of triangulations of the product of two simplices and the combinatorics of the associated set of bipartite graphs with an additional sign information. Finally, we establish an upper bound for our feasibility algorithm applied to a system of min-plus-inequalities in terms of the secondary fan of a product of two simplices. The appropriate complexity measure is a shortest integer vector in a cone of the secondary fan associated to the system.

MSC:

14T90 Applications of tropical geometry
90C05 Linear programming
52C40 Oriented matroids in discrete geometry
91A50 Discrete-time games
05E45 Combinatorial aspects of simplicial complexes
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] M. Akian, G. Cohen, S. Gaubert, R. Nikoukhah, and J. P. Quadrat. Linear systems in (max, +) algebra. In29th IEEE Conference on Decision and Control, pages 151-156 vol.1, Dec 1990.
[2] Marianne Akian, St´ephane Gaubert, and Alexander Guterman. Tropical polyhedra are equivalent to mean payoff games.Internat. J. Algebra Comput., 22(1):1250001, 43, 2012. · Zbl 1239.14054
[3] Marianne Akian, St´ephane Gaubert, and Alexander Guterman. Tropical Cramer determinants revisited. InTropical and idempotent mathematics and applications, volume 616 ofContemp. Math., pages 1-45. Amer. Math. Soc., Providence, RI, 2014. · Zbl 1320.14074
[4] Xavier Allamigeon, Pascal Benchimol, St´ephane Gaubert, and Michael Joswig. Combinatorial simplex algorithms can solve mean payoff games.SIAM J. Optim., 24(4):2096-2117, 2014. · Zbl 1336.90057
[5] Xavier Allamigeon, Pascal Benchimol, St´ephane Gaubert, and Michael Joswig. Tropicalizing the simplex algorithm.SIAM J. Discrete Math., 29(2):751-795, 2015. · Zbl 1334.14033
[6] Xavier Allamigeon, Pascal Benchimol, St´ephane Gaubert, and Michael Joswig. Logbarrier interior point methods are not strongly polynomial.SIAM J. Appl. Algebra Geom., 2(1):140-178, 2018. · Zbl 1391.90637
[7] Federico Ardila and Sara Billey. Flag arrangements and triangulations of products of simplices.Adv. Math., 214(2):495-524, 2007. · Zbl 1194.14078
[8] Federico Ardila and Mike Develin. Tropical hyperplane arrangements and oriented matroids.Math. Z., 262(4):795-816, 2009. · Zbl 1175.52024
[9] E. K. Babson and L. J. Billera. The geometry of products of minors.Discrete Comput. Geom., 20(2):231-249, 1998. · Zbl 0924.52005
[10] Pascal Benchimol.Tropical aspects of linear programming. Theses, ´Ecole Polytechnique, December 2014.
[11] Henrik Bj¨orklund and Sergei Vorobyov. A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games.Discrete Appl. Math., 155(2):210-229, 2007. · Zbl 1176.68087
[12] Robert G. Bland. A combinatorial abstraction of linear programming.J. Combinatorial Theory Ser. B, 23(1):33-57, 1977. · Zbl 0375.90046
[13] B´ela Bollob´as.Modern graph theory, volume 184 ofGraduate Texts in Mathematics. Springer-Verlag, New York, 1998. · Zbl 0902.05016
[14] P. Butkovic and A. Aminu. Introduction to max-linear programming.IMA J. Manag. Math., 20(3):233-249, 2009. · Zbl 1169.90396
[15] Peter Butkoviˇc.Max-linear systems: theory and algorithms. Springer Monographs in Mathematics. Springer-Verlag London, Ltd., London, 2010. · Zbl 1202.15032
[16] Peter Butkoviˇc and Karel Zimmermann. A strongly polynomial algorithm for solving two-sided linear systems in max-algebra.Discrete Appl. Math., 154(3):437-446, 2006. · Zbl 1090.68119
[17] Cristian Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan. Deciding parity games in quasipolynomial time. · Zbl 1369.68234
[18] George B. Dantzig.Linear programming and extensions. Princeton University Press, Princeton, N.J., 1963. · Zbl 0108.33103
[19] Jes´us A. De Loera, J¨org Rambau, and Francisco Santos.Triangulations, volume 25 of Algorithms and Computation in Mathematics. Springer-Verlag, Berlin, 2010. Structures for algorithms and applications. · Zbl 1207.52002
[20] Mike Develin and Bernd Sturmfels. Tropical convexity.Doc. Math., 9:1-27 (electronic), 2004. erratumibid., pp. 205-206. · Zbl 1054.52004
[21] Mike Develin and Josephine Yu. Tropical polytopes and cellular resolutions.Experiment. Math., 16(3):277-291, 2007. · Zbl 1134.52006
[22] Anton Dochtermann, Michael Joswig, and Raman Sanyal. Tropical types and associated cellular resolutions.J. Algebra, 356:304-324, 2012. · Zbl 1316.14116
[23] Dani Dorfman, Haim Kaplan, and Uri Zwick. A Faster Deterministic Exponential Time Algorithm for Energy Games and Mean Payoff Games. In Christel Baier, · Zbl 1522.91066
[24] A. Ehrenfeucht and J. Mycielski. Positional strategies for mean payoff games.Internat. J. Game Theory, 8(2):109-113, 1979. · Zbl 0499.90098
[25] E.A. Emerson and C.S. Jutla. Tree automata, mu-calculus and determinacy.2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 00:368-377, 1991.
[26] Nathana¨el Fijalkow, Pawe l Gawrychowski, and Pierre Ohlmann. The complexity of mean payoff games using universal graphs, 2018.
[27] Alex Fink and Felipe Rinc´on. Stiefel tropical linear spaces.J. Combin. Theory Ser. A, 135:291-331, 2015. · Zbl 1321.15044
[28] Andr´as Frank and ´Eva Tardos. An application of simultaneous Diophantine approximation in combinatorial optimization.Combinatorica, 7(1):49-65, 1987. · Zbl 0641.90067
[29] Oliver Friedmann.Exponential Lower Bounds for Solving Infinitary Payoff Games and Linear Programs. PhD thesis, University of Munich, 2011. · Zbl 1341.90143
[30] Komei Fukuda.Oriented matroid programming. ProQuest LLC, Ann Arbor, MI, 1982. Thesis (Ph.D.)-University of Waterloo (Canada).
[31] St´ephane Gaubert and Max Plus. Methods and applications of (max,+) linear algebra. InSTACS 97 (L¨ubeck), volume 1200 ofLecture Notes in Comput. Sci., pages 261-282. Springer, Berlin, 1997. · Zbl 1498.15034
[32] Ewgenij Gawrilow and Michael Joswig.polymake: a framework for analyzing convex polytopes. InPolytopes—combinatorics and computation (Oberwolfach, 1997), volume 29 ofDMV Sem., pages 43-73. Birkh¨auser, Basel, 2000. · Zbl 0960.68182
[33] I. M. Gel0fand, R. M. Goresky, R. D. MacPherson, and V. V. Serganova. Combinatorial geometries, convex polyhedra, and Schubert cells.Adv. in Math., 63(3):301-316, 1987. · Zbl 0622.57014
[34] I. M. Gel0fand, M. M. Kapranov, and A. V. Zelevinsky.Discriminants, resultants, and multidimensional determinants. Mathematics: Theory & Applications. Birkh¨auser Boston, Inc., Boston, MA, 1994. · Zbl 0827.14036
[35] Dima Grigoriev. Complexity of solving tropical linear systems.Comput. Complexity, 22(1):71-88, 2013. · Zbl 1282.68137
[36] Dima Grigoriev and Vladimir V. Podolskii. Tropical Effective Primary and Dual Nullstellens¨atze, 2014. preprintarXiv:1409.6215. · Zbl 1356.14058
[37] Dima Grigoriev and Vladimir V. Podolskii. Tropical effective primary and dual Nullstellens¨atze. In32nd International Symposium on Theoretical Aspects of Computer Science, volume 30 ofLIPIcs. Leibniz Int. Proc. Inform., pages 379-391. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2015. · Zbl 1356.14058
[38] V. A. Gurvich, A. V. Karzanov, and L. G. Khachiyan. Cyclic games and finding minimax mean cycles in digraphs.Zh. Vychisl. Mat. i Mat. Fiz., 28(9):1407-1417, 1439, 1988. · Zbl 0661.90108
[39] Thomas Dueholm Hansen.Worst-case Analysis of Strategy Iteration and the Simplex Method. PhD thesis, Aarhus University, 2012.
[40] Sven Herrmann, Anders Jensen, Michael Joswig, and Bernd Sturmfels.How to draw tropical planes.Electron. J. Combin., 16(2, Special volume in honor of Anders Bj¨orner):#R6, 26, 2009. · Zbl 1195.14080
[41] Silke Horn.The polymake extension tropmat.http://solros.de/polymake/ tropmat/.
[42] Silke Horn.Tropical Oriented Matroids and Cubical Complexes. PhD thesis, Technische Universit¨at Darmstadt, 2012. · Zbl 1327.52002
[43] Silke Horn. A topological representation theorem for tropical oriented matroids.J. Combin. Theory Ser. A, 142:77-112, 2016. · Zbl 1337.05113
[44] Marianne Johnson and Mark Kambites. Face monoid actions and tropical hyperplane arrangements.Int. J. Algebra Comput., 27(8):1001-1025, 2017. · Zbl 1392.52013
[45] Michael Joswig and Georg Loho. Weighted digraphs and tropical cones.Linear Algebra Appl., 501:304-343, 2016. · Zbl 1405.14141
[46] Marcin Jurdzi´nski. Deciding the winner in parity games is in UP∩co-UP.Inform. Process. Lett., 68(3):119-124, 1998. · Zbl 1338.68109
[47] N. Karmarkar. A new polynomial-time algorithm for linear programming.Combinatorica, 4(4):373-395, 1984. · Zbl 0557.90065
[48] Leonid Khachiyan. A polynomial algorithm in linear programming.Dokl. Akad. Nauk SSSR, 244(5):1093-1096, 1979. · Zbl 0414.90086
[49] Victor Klee and George J. Minty. How good is the simplex algorithm? InInequalities, III (Proc. Third Sympos., Univ. California, Los Angeles, Calif., 1969; dedicated to the memory of Theodore S. Motzkin), pages 159-175. Academic Press, New York, 1972. · Zbl 0297.90047
[50] A. K. Lenstra, H. W. Lenstra, Jr., and L. Lov´asz. Factoring polynomials with rational coefficients.Math. Ann., 261(4):515-534, 1982. · Zbl 0488.12001
[51] Georg Loho.Combinatorics of tropical linear programming. PhD thesis, Technische Universit¨at Berlin, 2017.
[52] Rolf H. M¨ohring, Martin Skutella, and Frederik Stork. Scheduling with AND/OR precedence constraints.SIAM J. Comput., 33(2):393-415, 2004. · Zbl 1112.90034
[53] Katta G. Murty.Linear and combinatorial programming. John Wiley & Sons, Inc., New York-London-Sydney, 1976. · Zbl 0334.90032
[54] Suho Oh and Hwanchul Yoo. Triangulations of ∆n−1×∆d−1and tropical oriented matroids. In23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), Discrete Math. Theor. Comput. Sci. Proc., AO, pages 717-728. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2011. · Zbl 1366.52025
[55] Suho Oh and Hwanchul Yoo. Triangulations of ∆n−1×∆d−1and Matching Ensembles, 2013. preprintarXiv:1311.6772. · Zbl 1366.52025
[56] Alexander Postnikov. Permutohedra, associahedra, and beyond.Int. Math. Res. Not. IMRN, 2009(6):1026-1106, 2009. · Zbl 1162.52007
[57] J¨urgen Richter-Gebert.Realization spaces of polytopes, volume 1643 ofLecture Notes in Mathematics. Springer-Verlag, Berlin, 1996.
[58] J¨urgen Richter-Gebert, Bernd Sturmfels, and Thorsten Theobald. First steps in tropical geometry. InIdempotent mathematics and mathematical physics, volume 377 ofContemp. Math., pages 289-317. Amer. Math. Soc., Providence, RI, 2005. · Zbl 1093.14080
[59] R. T. Rockafellar. The elementary vectors of a subspace ofRN. InCombinatorial Mathematics and its Applications (Proc. Conf., Univ. North Carolina, Chapel Hill, N.C., 1967), pages 104-127. Univ. North Carolina Press, Chapel Hill, N.C., 1969. · Zbl 0229.90019
[60] Francisco Santos. Triangulations of oriented matroids.Mem. Amer. Math. Soc., 156(741):viii+80, 2002. · Zbl 1006.52017
[61] Francisco Santos. The Cayley trick and triangulations of products of simplices. In Integer points in polyhedra—geometry, number theory, algebra, optimization, volume 374 ofContemp. Math., pages 151-177. Amer. Math. Soc., Providence, RI, 2005. · Zbl 1079.52508
[62] Sven Schewe. From parity and payoff games to linear programming. InMathematical foundations of computer science 2009, volume 5734 ofLecture Notes in Comput. Sci., pages 675-686. Springer, Berlin, 2009. · Zbl 1250.68131
[63] Bernd Sturmfels and Andrei Zelevinsky. Maximal minors and their leading terms. Adv. Math., 98(1):65-112, 1993. · Zbl 0776.13009
[64] Tam´as Terlaky. A finite criss-cross method for oriented matroids.Alkalmaz. Mat. Lapok, 11(3-4):385-398, 1985. · Zbl 0609.05027
[65] Michael J. Todd. Complementarity in oriented matroids.SIAM J. Algebraic Discrete Methods, 5(4):467-485, 1984. · Zbl 0556.05016
[66] Michael J. Todd. Linear and quadratic programming in oriented matroids.J. Combin. Theory Ser. B, 39(2):105-133, 1985. · Zbl 0555.05026
[67] Oleg Viro.Dequantization of real algebraic geometry on logarithmic paper.In European Congress of Mathematics, Vol. I (Barcelona, 2000), volume 201 ofProgr. Math., pages 135-146. Birkh¨auser, Basel, 2001. · Zbl 1024.14026
[68] G¨unter M. Ziegler.Lectures on polytopes, volume 152 ofGraduate Texts in Mathematics. Springer-Verlag, New York, 1995. · Zbl 0823.52002
[69] Uri Zwick and Mike Paterson. The complexity of mean payoff games on graphs. Theoret. Comput. Sci., 158(1-2):343-359, 1996. · Zbl 0871.68138
[70] ) = (0,0,Ω4,Ω4+ 2) has a totally infeasible covector graph.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.