×

Tropical polar cones, hypergraph transversals, and mean payoff games. (English) Zbl 1217.14047

Summary: We discuss the tropical analogues of several basic questions of convex duality. In particular, the polar of a tropical polyhedral cone represents the set of linear inequalities that its elements satisfy. We characterize the extreme rays of the polar in terms of certain minimal set covers which may be thought of as weighted generalizations of minimal transversals in hypergraphs. We also give a tropical analogue of Farkas lemma, which allows one to check whether a linear inequality is implied by a finite family of linear inequalities. Here, the certificate is a strategy of a mean payoff game. We discuss examples, showing that the number of extreme rays of the polar of the tropical cyclic polyhedral cone is polynomially bounded, and that there is no unique minimal system of inequalities defining a given tropical polyhedral cone.

MSC:

14T05 Tropical geometry (MSC2010)
15A80 Max-plus and related algebras
52A01 Axiomatic and generalized convexity
16Y60 Semirings

Software:

TPLib
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] M. Akian, S. Gaubert, A. Guterman, Tropical polyhedra are equivalent to mean payoff games, 2009. Available from: <arXiv:0912.2462v1>; M. Akian, S. Gaubert, A. Guterman, Tropical polyhedra are equivalent to mean payoff games, 2009. Available from: <arXiv:0912.2462v1> · Zbl 1239.14054
[2] X. Allamigeon, S. Gaubert, É. Goubault, Computing the extreme points of tropical polyhedra, 2009. Available from: <arXiv:0904.3436>[4]; X. Allamigeon, S. Gaubert, É. Goubault, Computing the extreme points of tropical polyhedra, 2009. Available from: <arXiv:0904.3436>[4]
[3] M. Akian, S. Gaubert, A. Guterman, The correspondence between tropical convexity and mean payoff games, in: Proceedings of the 19th International Symposium on Mathematical Theory of Networks and Systems (MTNS 2010), 5-9 July, Budapest, Hungary, 2010, pp. 1295-1302.; M. Akian, S. Gaubert, A. Guterman, The correspondence between tropical convexity and mean payoff games, in: Proceedings of the 19th International Symposium on Mathematical Theory of Networks and Systems (MTNS 2010), 5-9 July, Budapest, Hungary, 2010, pp. 1295-1302.
[4] X. Allamigeon, S. Gaubert, É. Goubault, The tropical double description method, in: J.-Y. Marion, Th. Schwentick (Eds.), Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010), Volume 5 of Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, 2010, pp. 47-58 (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik).; X. Allamigeon, S. Gaubert, É. Goubault, The tropical double description method, in: J.-Y. Marion, Th. Schwentick (Eds.), Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010), Volume 5 of Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, 2010, pp. 47-58 (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik). · Zbl 1230.52024
[5] Allamigeon, X.; Gaubert, S.; Katz, R. D., The number of extreme points of tropical polyhedra, J. Combin. Theory Ser. A, 118, 1, 162-189 (2011), Available from: · Zbl 1246.14078
[6] X. Allamigeon, Static analysis of memory manipulations by abstract interpretation — algorithmics of tropical polyhedra, and application to abstract interpretation, Ph.D. thesis, École Polytechnique, Palaiseau, France, November 2009. Available from: <http://www.lix.polytechnique.fr/Labo/Xavier.Allamigeon/papers/thesis.pdf; X. Allamigeon, Static analysis of memory manipulations by abstract interpretation — algorithmics of tropical polyhedra, and application to abstract interpretation, Ph.D. thesis, École Polytechnique, Palaiseau, France, November 2009. Available from: <http://www.lix.polytechnique.fr/Labo/Xavier.Allamigeon/papers/thesis.pdf
[7] X. Allamigeon, TPLib: tropical polyhedra library in OCaml, 2009. Available from: <http://penjili.org/tplib.html; X. Allamigeon, TPLib: tropical polyhedra library in OCaml, 2009. Available from: <http://penjili.org/tplib.html
[8] Baccelli, F.; Cohen, G.; Olsder, G.-J.; Quadrat, J.-P., Synchronization and Linearity (1992), Wiley
[9] Boros, E.; Elbassioni, K.; Gurvich, V.; Khachiyan, L.; Makino, K., Dual-bounded generating problems: all minimal integer solutions for a monotone system of linear inequalities, SIAM J. Comput., 31, 5, 1624-1643 (2002) · Zbl 1041.68064
[10] Butkovič, P.; Hegedüs, G., An elimination method for finding all solutions of the system of linear equations over an extremal algebra, Ekonomicko-matematicky Obzor, 20, 2, 203-215 (1984)
[11] Briec, W.; Horvath, C., \(B\)-convexity, Optimization, 53, 103-127 (2004) · Zbl 1144.90506
[12] M. Bezem, R. Nieuwenhuis, E. Rodrı´guez-Carbonell, The max-atom problem and its relevance, in: I. Cervesato, H. Veith, A. Voronkov (Eds.), Proceedings of the 15th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR’08, Lecture Notes in Comput. Sci., vol. 5330, Springer, 2008, pp. 47-61.; M. Bezem, R. Nieuwenhuis, E. Rodrı´guez-Carbonell, The max-atom problem and its relevance, in: I. Cervesato, H. Veith, A. Voronkov (Eds.), Proceedings of the 15th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR’08, Lecture Notes in Comput. Sci., vol. 5330, Springer, 2008, pp. 47-61. · Zbl 1182.68219
[13] Bezem, M.; Nieuwenhuis, R.; Rodríguez-Carbonell, E., Hard problems in max-algebra, control theory, hypergraphs and other areas, Inform. Process. Lett., 110, 133-138 (2010) · Zbl 1206.68284
[14] Butkovič, P.; Schneider, H.; Sergeev, S., Generators, extremals and bases of max cones, Linear Algebra Appl., 421, 2-3, 394-406 (2007), Available from: · Zbl 1119.15018
[15] Block, F.; Yu, J., Tropical convexity via cellular resolutions, J. Algebraic Combin., 24, 1, 103-114 (2006), Available from: · Zbl 1097.52506
[16] Cuninghame-Green, R. A., Minimax Algebra, Lecture Notes in Econom. and Math. Systems, vol. 166 (1979), Springer-Verlag: Springer-Verlag Berlin · Zbl 0399.90052
[17] Cohen, G.; Gaubert, S.; Quadrat, J. P., Duality and separation theorems in idempotent semimodules, Linear Algebra Appl., 379, 395-422 (2004), Available from: · Zbl 1042.46004
[18] G. Cohen, S. Gaubert, J.P. Quadrat, I. Singer, Max-plus convex sets and functions, in: G.L. Litvinov, V.P. Maslov (Eds.), Idempotent Mathematics and Mathematical Physics, Contemporary Mathematics, American Mathematical Society, vol. 377, 2005, pp. 105-129. Also ESI Preprint 1341, <arXiv:math.FA/0308166>; G. Cohen, S. Gaubert, J.P. Quadrat, I. Singer, Max-plus convex sets and functions, in: G.L. Litvinov, V.P. Maslov (Eds.), Idempotent Mathematics and Mathematical Physics, Contemporary Mathematics, American Mathematical Society, vol. 377, 2005, pp. 105-129. Also ESI Preprint 1341, <arXiv:math.FA/0308166> · Zbl 1093.26005
[19] J. Cochet-Terrasson, G. Cohen, S. Gaubert, M.M. Gettrick, J.P. Quadrat, Numerical computation of spectral elements in max-plus algebra, in: Proceedings of the IFAC Conference on Systems Structure and Control, IRCT, Nantes, France, 1998, pp. 699-706.; J. Cochet-Terrasson, G. Cohen, S. Gaubert, M.M. Gettrick, J.P. Quadrat, Numerical computation of spectral elements in max-plus algebra, in: Proceedings of the IFAC Conference on Systems Structure and Control, IRCT, Nantes, France, 1998, pp. 699-706.
[20] Cochet-Terrasson, J.; Gaubert, S.; Gunawardena, J., A constructive fixed point theorem for min-max functions, Dyn. Stab. Syst., 14, 4, 407-433 (1999) · Zbl 0958.47028
[21] Develin, M.; Sturmfels, B., Tropical convexity, Doc. Math., 9, 1-27 (2004), Available from: · Zbl 1054.52004
[22] Elbassioni, K. M., A note on systems with max-min and max-product constraints, Fuzzy Sets and Systems, 159, 17, 2272-2277 (2008) · Zbl 1178.90357
[23] Fredman, M. L.; Khachiyan, L., On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms, 21, 618-628 (1996) · Zbl 0864.68038
[24] S. Gaubert, Théorie des systèmes linéaires dans les dioı¨des, Thèse, École des Mines de Paris, July 1992.; S. Gaubert, Théorie des systèmes linéaires dans les dioı¨des, Thèse, École des Mines de Paris, July 1992.
[25] Gaubert, S.; Gunawardena, J., The duality theorem for min-max functions, C.R. Acad. Sci. Paris, 326, 43-48 (1998), Série I · Zbl 0933.49017
[26] S. Gaubert, J. Gunawardena, A non-linear hierarchy for discrete event dynamical systems, in: Proceedings of the Fourth Workshop on Discrete Event Systems (WODES98), IEE, Cagliari, Italy, 1998.; S. Gaubert, J. Gunawardena, A non-linear hierarchy for discrete event dynamical systems, in: Proceedings of the Fourth Workshop on Discrete Event Systems (WODES98), IEE, Cagliari, Italy, 1998. · Zbl 0933.49017
[27] Gaubert, S.; Gunawardena, J., The Perron-Frobenius theorem for homogeneous, monotone functions, Trans. Amer. Math. Soc., 356, 12, 4931-4950 (2004) · Zbl 1067.47064
[28] S. Gaubert, R.D. Katz, Max-plus convex geometry, in: R.A. Schmidt (Ed.), Proceedings of the 9th International Conference on Relational Methods in Computer Science and 4th International Workshop on Applications of Kleene Algebra (RelMiCS/AKA 2006), Lecture Notes in Comput. Sci., vol. 4136, Springer, 2006, pp. 192-206.; S. Gaubert, R.D. Katz, Max-plus convex geometry, in: R.A. Schmidt (Ed.), Proceedings of the 9th International Conference on Relational Methods in Computer Science and 4th International Workshop on Applications of Kleene Algebra (RelMiCS/AKA 2006), Lecture Notes in Comput. Sci., vol. 4136, Springer, 2006, pp. 192-206. · Zbl 1134.52303
[29] Gaubert, S.; Katz, R. D., The Minkowski theorem for max-plus convex sets, Linear Algebra Appl., 421, 2-3, 356-369 (2007), Available from: · Zbl 1110.52002
[30] Gaubert, S.; Katz, R. D., The tropical analogue of polar cones, Linear Algebra Appl., 431, 5-7, 608-625 (2009), Available from: · Zbl 1172.52002
[31] Gaubert, S.; Katz, R. D., Minimal half-spaces and external representation of tropical polyhedra, J. Algebraic Combin., 33, 3, 325-348 (2011), Available from: · Zbl 1218.52001
[32] Gurvich, V. A.; Karzanov, A. V.; Khachiyan, L. G., Cyclic games and finding minimax mean cycles in digraphs, Zh. Vychisl. Mat. i Mat. Fiz., 28, 9, 1407-1417 (1988), 1439 · Zbl 0661.90108
[33] Gaubert, S.; Meunier, F., Carathéodory, Helly and the others in the max-plus world, Discrete Comput. Geom., 43, 3, 648-662 (2010), Available from: · Zbl 1219.14071
[34] S. Gaubert, M. Plus, Methods and applications of (max,+) linear algebra, in: R. Reischuk, M. Morvan (Eds.), Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS’97), Lecture Notes in Comput. Sci., vol. 1200, Lübeck, March 1997, Springer.; S. Gaubert, M. Plus, Methods and applications of (max,+) linear algebra, in: R. Reischuk, M. Morvan (Eds.), Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS’97), Lecture Notes in Comput. Sci., vol. 1200, Lübeck, March 1997, Springer.
[35] S. Gaubert, S. Sergeev, The level set method for the two-sided max-plus eigenproblem, 2010. Available from: <arXiv:1006.5702>; S. Gaubert, S. Sergeev, The level set method for the two-sided max-plus eigenproblem, 2010. Available from: <arXiv:1006.5702>
[36] M. Joswig, Tropical halfspaces, in: Combinatorial and Computational Geometry, Math. Sci. Res. Inst. Publ., vol. 52, Cambridge Univ. Press, Cambridge, 2005, pp. 409-431. Available from: <arXiv:math.CO/0312068>; M. Joswig, Tropical halfspaces, in: Combinatorial and Computational Geometry, Math. Sci. Res. Inst. Publ., vol. 52, Cambridge Univ. Press, Cambridge, 2005, pp. 409-431. Available from: <arXiv:math.CO/0312068> · Zbl 1090.52500
[37] M. Joswig, Tropical convex hull computations, in: G.L. Litvinov, S.N. Sergeev (Eds.), Proceedings of the International Conference on Tropical and Idempotent Mathematics, Contemporary Mathematics, vol. 495, American Mathematical Society, 2009, pp. 193-212.; M. Joswig, Tropical convex hull computations, in: G.L. Litvinov, S.N. Sergeev (Eds.), Proceedings of the International Conference on Tropical and Idempotent Mathematics, Contemporary Mathematics, vol. 495, American Mathematical Society, 2009, pp. 193-212. · Zbl 1202.52004
[38] Joswig, M.; Sturmfels, B.; Yu, J., Affine buildings and tropical convexity, Albanian J. Math., 1, 4, 187-211 (2007), Available from: · Zbl 1133.52003
[39] Khachiyan, L.; Boros, E.; Elbassioni, K.; Gurvich, V., An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation, Discrete Appl. Math., 154, 16, 2350-2372 (2006) · Zbl 1110.68104
[40] Kohlberg, E., Invariant half-lines of nonexpansive piecewise-linear transformations, Math. Oper. Res., 5, 3, 366-372 (1980) · Zbl 0442.90102
[41] Liggett, T. M.; Lippman, S. A., Stochastic games with perfect information and time average payoff, SIAM Rev., 11, 604-607 (1969) · Zbl 0193.19602
[42] Litvinov, G. L.; Maslov, V. P.; Shpiz, G. B., Idempotent functional analysis: an algebraic approach, Math. Notes, 69, 5, 696-729 (2001), Available from: · Zbl 1017.46034
[43] Matoušek, J., Lectures on Discrete Geometry, Graduate Texts in Mathematics (2002), Springer-Verlag: Springer-Verlag New York · Zbl 0999.52006
[44] McMullen, P., The maximum numbers of faces of a convex polytope, Mathematika, 17, 179-184 (1970) · Zbl 0217.46703
[45] Möhring, R. H.; Skutella, M.; Stork, F., Scheduling with AND/OR precedence constraints, SIAM J. Comput., 33, 2, 393-415 (2004), (electronic) · Zbl 1112.90034
[46] Samborskiı˘, S. N.; Shpiz, G. B., Convex Sets in the Semimodule of Bounded Functions, (Idempotent Analysis (1992), American Mathematical Society: American Mathematical Society Providence, RI), 135-137 · Zbl 0896.47030
[47] Ziegler, G. M., Lectures on Polytopes (1998), Springer-Verlag: Springer-Verlag New York · Zbl 0898.52006
[48] Zimmermann, K., A general separation theorem in extremal algebras, Ekonomicko-matematicky Obzor, 13, 2, 179-201 (1977)
[49] Zwick, U.; Paterson, M., The complexity of mean payoff games on graphs, Theoret. Comput. Sci., 158, 1-2, 343-359 (1996) · Zbl 0871.68138
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.