Minimal half-spaces and external representation of tropical polyhedra
Stéphane Gaubert
and Ricardo D. Katz
DOI: 10.1007/s10801-010-0246-4
Abstract
We give a characterization of the minimal tropical half-spaces containing a given tropical polyhedron, from which we derive a counter-example showing that the number of such minimal half-spaces can be infinite, contradicting some statements which appeared in the tropical literature, and disproving a conjecture of F. Block and J. Yu. We also establish an analogue of the Minkowski-Weyl theorem, showing that a tropical polyhedron can be equivalently represented internally (in terms of extreme points and rays) or externally (in terms of half-spaces containing it). A canonical external representation of a polyhedron turns out to be provided by the extreme elements of its tropical polar. We characterize these extreme elements, showing in particular that they are determined by support vectors.
Pages: 325–348
Keywords: keywords max-plus semiring; max-plus convexity; tropical convexity; polyhedra; polytopes; Minkowski-Weyl theorem; supporting half-spaces
Full Text: PDF
References
1. Akian, M., Gaubert, S., Kolokoltsov, V.N.: Set coverings and invertibility of functional Galois connections. In: Litvinov, G.L., Maslov, V.P. (eds.) Idempotent Mathematics and Mathematical Physics. Contemporary Mathematics, pp. 19-51. American Mathematical Society, Providence (2005). Also ESI Preprint 1447, arXi
2. Akian, M., Bapat, R., Gaubert, S.: Max-plus algebras. In: Hogben, L. (ed.) Handbook of Linear Al- gebra. Discrete Mathematics and Its Applications, vol.
39. Chapman & Hall/CRC, London (2006). Chap. 25
3. Allamigeon, X., Gaubert, S., Goubault, É.: Computing the extreme points of tropical polyhedra. Eprint arXiv:(v2) (2009)
4. Allamigeon, X., Gaubert, S., Goubault, É.: The tropical double description method. In: Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, STACS'2010, March 4-6, Nancy, France. Leibniz Center in Informatics (2010)
5. Allamigeon, X., Gaubert, S., Katz, R.D.: The number of extreme points of tropical polyhedra. J. Comb. Theory Ser. A (to appear). Also Eprint arXiv:
6. Block, F., Yu, J.: Tropical convexity via cellular resolutions. J. Algebr. Comb. 24(1), 103-114 (2006). Also eprint arXiv:
7. Briec, W., Horvath, C.: B-convexity. Optimization 53, 103-127 (2004)
8. Briec, W., Horvath, C.: Halfspaces and Hahn-Banach like properties in B-convexity and max-plus convexity. Pac. J. Optim. 4(2), 293-317 (2008)
9. Butkovi\check c, P., Hegedüs, G.: An elimination method for finding all solutions of the system of linear equations over an extremal algebra. Ekon.-Mat. Obz. 20(2), 203-215 (1984)
10. Butkovi\check c, P., Schneider, H., Sergeev, S.: Generators, extremals and bases of max cones. Linear Algebra Appl. 421(2-3), 394-406 (2007). Also eprint arXiv:
11. Cohen, G., Gaubert, S., Quadrat, J.P.: Max-plus algebra and system theory: where we are and where to go now. Annu. Rev. Control 23, 207-219 (1999)
12. Cohen, G., Gaubert, S., Quadrat, J.P.: Hahn-Banach separation theorem for max-plus semimodules. In: Menaldi, J.L., Rofman, E., Sulem, A. (eds.) Optimal Control and Partial Differential Equations, pp. 325-334. IOS Press, Amsterdam (2001) J Algebr Comb (2011) 33: 325-348
13. Cohen, G., Gaubert, S., Quadrat, J.P.: Duality and separation theorems in idempotent semimodules. Linear Algebra Appl. 379, 395-422 (2004). doi:, arXiv
14. Cohen, G., Gaubert, S., Quadrat, J.P., Singer, I.: Max-plus convex sets and functions. In: Litvinov, G.L., Maslov, V.P. (eds.) Idempotent Mathematics and Mathematical Physics. Contemporary Mathematics, pp. 105-129. American Mathematical Society, Providence (2005). Also ESI Preprint 1341, arXiv:
15. Cohen, G., Gaubert, S., McGettrick, M., Quadrat, J.P.: Maxplus toolbox of SCILAB. Available at now integrated into SCICOSLAB.
16. Develin, M., Sturmfels, B.: Tropical convexity. Doc. Math. 9, 1-27 (2004) (Erratum pp. 205-206). Also eprint arXiv:
17. Engel, K.: Sperner Theory. Encyclopedia of Mathematics and Its Applications, vol.
65. Cambridge University Press, Cambridge (1997)
18. Gaubert, S.: Théorie des systèmes linéaires dans les dioïdes. Thèse, École des Mines de Paris (July 1992)
19. Gaubert, S., Katz, R.D.: Max-plus convex geometry. In: Schmidt, R.A. (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, pp. 192-206. Springer, Berlin (2006)
20. Gaubert, S., Katz, R.D.: The Minkowski theorem for max-plus convex sets. Linear Algebra Appl. 421(2-3), 356-369 (2007). Also eprint arXiv:
21. Gaubert, S., Katz, R.D.: The tropical analogue of polar cones. Linear Algebra Appl. 431(5-7), 608- 625 (2009). Also eprint arXiv:
22. Gaubert, S., Meunier, F.: Carathéodory, Helly and the others in the max-plus world. Discrete Comput. Geom. 43(3), 648-662 (2010). Also eprint arXiv
23. Gaubert, S., Plus, M.: Methods and applications of (max,+) linear algebra. In: Reischuk, R., Morvan, M. (eds.) STACS'97, Lübeck, Lecture Notes in Comput. Sci., vol.
1200. Springer, Berlin (March 1997)
24. Gaubert, S., Sergeev, S.N.: Cyclic projectors and separation theorems in idempotent convex geometry. J. Math. Sci. 155(6), 815-829 (2008). Russian version published in Fundam. Prikl. Mat. 13(4), 33-52 (2007)
25. Gawrilow, E., Joswig, M.: POLYMAKE: a framework for analyzing convex polytopes. In: Kalai, G., Ziegler, G.M. (eds.) Polytopes-Combinatorics and Computation, pp. 43-74. Birkhäuser, Basel (2000).
26. Joswig M.: Tropical halfspaces. In: Combinatorial and Computational Geometry. Math. Sci. Res. Inst. Publ., vol. 52, pp. 409-431. Cambridge Univ. Press, Cambridge (2005). Also eprint arXiv:
27. Joswig M.: Tropical convex hull computations. In: Litvinov, G.L., Sergeev, S.N. (eds.) Proceedings of the International Conference on Tropical and Idempotent Mathematics. Contemporary Mathematics, vol. 495, pp. 193-212. American Mathematical Society, Providence (2009). Also eprint arXiv:
28. Joswig, M., Sturmfels, B., Yu J.: Affine buildings and tropical convexity. Albanian J. Math. 1(4), 187-211 (2007). Also eprint arXiv:
29. Litvinov, G.L., Maslov, V.P., Shpiz G.B.: Idempotent functional analysis: an algebraic approach.
2. Akian, M., Bapat, R., Gaubert, S.: Max-plus algebras. In: Hogben, L. (ed.) Handbook of Linear Al- gebra. Discrete Mathematics and Its Applications, vol.
39. Chapman & Hall/CRC, London (2006). Chap. 25
3. Allamigeon, X., Gaubert, S., Goubault, É.: Computing the extreme points of tropical polyhedra. Eprint arXiv:(v2) (2009)
4. Allamigeon, X., Gaubert, S., Goubault, É.: The tropical double description method. In: Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, STACS'2010, March 4-6, Nancy, France. Leibniz Center in Informatics (2010)
5. Allamigeon, X., Gaubert, S., Katz, R.D.: The number of extreme points of tropical polyhedra. J. Comb. Theory Ser. A (to appear). Also Eprint arXiv:
6. Block, F., Yu, J.: Tropical convexity via cellular resolutions. J. Algebr. Comb. 24(1), 103-114 (2006). Also eprint arXiv:
7. Briec, W., Horvath, C.: B-convexity. Optimization 53, 103-127 (2004)
8. Briec, W., Horvath, C.: Halfspaces and Hahn-Banach like properties in B-convexity and max-plus convexity. Pac. J. Optim. 4(2), 293-317 (2008)
9. Butkovi\check c, P., Hegedüs, G.: An elimination method for finding all solutions of the system of linear equations over an extremal algebra. Ekon.-Mat. Obz. 20(2), 203-215 (1984)
10. Butkovi\check c, P., Schneider, H., Sergeev, S.: Generators, extremals and bases of max cones. Linear Algebra Appl. 421(2-3), 394-406 (2007). Also eprint arXiv:
11. Cohen, G., Gaubert, S., Quadrat, J.P.: Max-plus algebra and system theory: where we are and where to go now. Annu. Rev. Control 23, 207-219 (1999)
12. Cohen, G., Gaubert, S., Quadrat, J.P.: Hahn-Banach separation theorem for max-plus semimodules. In: Menaldi, J.L., Rofman, E., Sulem, A. (eds.) Optimal Control and Partial Differential Equations, pp. 325-334. IOS Press, Amsterdam (2001) J Algebr Comb (2011) 33: 325-348
13. Cohen, G., Gaubert, S., Quadrat, J.P.: Duality and separation theorems in idempotent semimodules. Linear Algebra Appl. 379, 395-422 (2004). doi:, arXiv
14. Cohen, G., Gaubert, S., Quadrat, J.P., Singer, I.: Max-plus convex sets and functions. In: Litvinov, G.L., Maslov, V.P. (eds.) Idempotent Mathematics and Mathematical Physics. Contemporary Mathematics, pp. 105-129. American Mathematical Society, Providence (2005). Also ESI Preprint 1341, arXiv:
15. Cohen, G., Gaubert, S., McGettrick, M., Quadrat, J.P.: Maxplus toolbox of SCILAB. Available at now integrated into SCICOSLAB.
16. Develin, M., Sturmfels, B.: Tropical convexity. Doc. Math. 9, 1-27 (2004) (Erratum pp. 205-206). Also eprint arXiv:
17. Engel, K.: Sperner Theory. Encyclopedia of Mathematics and Its Applications, vol.
65. Cambridge University Press, Cambridge (1997)
18. Gaubert, S.: Théorie des systèmes linéaires dans les dioïdes. Thèse, École des Mines de Paris (July 1992)
19. Gaubert, S., Katz, R.D.: Max-plus convex geometry. In: Schmidt, R.A. (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, pp. 192-206. Springer, Berlin (2006)
20. Gaubert, S., Katz, R.D.: The Minkowski theorem for max-plus convex sets. Linear Algebra Appl. 421(2-3), 356-369 (2007). Also eprint arXiv:
21. Gaubert, S., Katz, R.D.: The tropical analogue of polar cones. Linear Algebra Appl. 431(5-7), 608- 625 (2009). Also eprint arXiv:
22. Gaubert, S., Meunier, F.: Carathéodory, Helly and the others in the max-plus world. Discrete Comput. Geom. 43(3), 648-662 (2010). Also eprint arXiv
23. Gaubert, S., Plus, M.: Methods and applications of (max,+) linear algebra. In: Reischuk, R., Morvan, M. (eds.) STACS'97, Lübeck, Lecture Notes in Comput. Sci., vol.
1200. Springer, Berlin (March 1997)
24. Gaubert, S., Sergeev, S.N.: Cyclic projectors and separation theorems in idempotent convex geometry. J. Math. Sci. 155(6), 815-829 (2008). Russian version published in Fundam. Prikl. Mat. 13(4), 33-52 (2007)
25. Gawrilow, E., Joswig, M.: POLYMAKE: a framework for analyzing convex polytopes. In: Kalai, G., Ziegler, G.M. (eds.) Polytopes-Combinatorics and Computation, pp. 43-74. Birkhäuser, Basel (2000).
26. Joswig M.: Tropical halfspaces. In: Combinatorial and Computational Geometry. Math. Sci. Res. Inst. Publ., vol. 52, pp. 409-431. Cambridge Univ. Press, Cambridge (2005). Also eprint arXiv:
27. Joswig M.: Tropical convex hull computations. In: Litvinov, G.L., Sergeev, S.N. (eds.) Proceedings of the International Conference on Tropical and Idempotent Mathematics. Contemporary Mathematics, vol. 495, pp. 193-212. American Mathematical Society, Providence (2009). Also eprint arXiv:
28. Joswig, M., Sturmfels, B., Yu J.: Affine buildings and tropical convexity. Albanian J. Math. 1(4), 187-211 (2007). Also eprint arXiv:
29. Litvinov, G.L., Maslov, V.P., Shpiz G.B.: Idempotent functional analysis: an algebraic approach.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition