Approximating the volume of tropical polytopes is difficult. (English) Zbl 1420.14139
Summary: We investigate the complexity of counting the number of integer points in tropical polytopes, and the complexity of calculating their volume. We study the tropical analogue of the outer parallel body and establish bounds for its volume. We deduce that there is no approximation algorithm of factor \(\alpha=2^{\text{poly}(m,n)}\) for the volume of a tropical polytope given by \(n\) for the volume of a tropical polytope given by \(n\) vertices in a space of dimension \(m\), unless P=NP. Neither is there such an approximation algorithm for counting the number of integer points in tropical polytopes described by vertices. It follows that approximating these values for tropical polytopes is more difficult than for classical polytopes. Our proofs use a reduction from the problem of calculating the tropical rank.
MSC:
| 14T05 | Tropical geometry (MSC2010) |
| 52B55 | Computational aspects related to convexity |
| 16Y60 | Semirings |
| 14Q20 | Effectivity, complexity and computational aspects of algebraic geometry |
Keywords:
volume; counting integer points; tropical geometry; polytopes; approximation algorithms; computational complexity; outer parallel body; hilbert’s projective metricReferences:
| [1] | Akian, M., Bapat, R. and Gaubert, S., Max-plus algebras, in Handbook of Linear Algebra (Discrete Mathematics and its Applications), ed. Hogben, L., Vol, 39 (Chapman & Hall/CRC, 2013, 2006). · Zbl 0922.15001 |
| [2] | Allamigeon, X., Benchimol, P., Gaubert, S. and Joswig, M., Tropicalizing the simplex algorithm, SIAM J. Discr. Math.29(2) (2015) 751-795. · Zbl 1334.14033 |
| [3] | Allamigeon, X., Benchimol, P., Gaubert, S. and Joswig, M., Log-barrier interior point methods are not strongly polynomial, SIAM J. Appl. Algebra Geometry2(1) (2018) 140-178. · Zbl 1391.90637 |
| [4] | Allamigeon, X., Fahrenberg, U., Gaubert, S., Legay, A. and Katz, R., Tropical Fourier-Motzkin elimination, with an application to real-time verification, Int. J. Algebra Comput.24(5) (2014) 569-607. · Zbl 1301.90069 |
| [5] | Allamigeon, X., Gaubert, S. and Goubault, E., Inferring min and max invariants using max-plus polyhedra, in Proc. 15th Int. Static Analysis Symp. (SAS’08), LNCS, Vol. 5079 (Springer, Valencia, Spain, 2008), pp. 189-204. · Zbl 1149.68346 |
| [6] | Akian, M., Gaubert, S. and Guterman, A., Tropical polyhedra are equivalent to mean payoff games, Int. J. Algebra Comput.22(1) (2012) 125001, 43 pp. · Zbl 1239.14054 |
| [7] | Akian, M., Gaubert, S. and Walsh, C., The max-plus Martin boundary, Doc. Math.14 (2009) 195-240. · Zbl 1182.31017 |
| [8] | Allamigeon, X. and Katz, R. D., Minimal external representations of tropical polyhedra, J. Combin. Theory Ser. A120(4) (2013) 907-940. · Zbl 1312.52002 |
| [9] | Barvinok, A. I., A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed, Math. Oper. Res.19(4) (1994) 769-779. · Zbl 0821.90085 |
| [10] | Baccelli, F., Cohen, G., Olsder, G. J. and Quadrat, J. P., Synchronization and Linearity. (John Wiley & Sons, Ltd., Chichester, 1992). · Zbl 0824.93003 |
| [11] | Beck, M., De Loera, J. A., Develin, M., Pfeifle, J. and Stanley, R. P., Coefficients and roots of Ehrhart polynomials, in Integer Points in Polyhedra — Geometry, Number Theory, Algebra, Optimization, Contemporary Mathematics, Vol. 374 (American Mathematical Society, Providence, RI, 2005), pp. 15-36. · Zbl 1153.52300 |
| [12] | Bárány, I. and Füredi, Z., Computing the volume is difficult, Discr. Comput. Geom.2(4) (1987) 319-326. · Zbl 0628.68041 |
| [13] | Butkovič, P. and Hevery, F., A condition for the strong regularity of matrices in the minimax algebra, Discr. Appl. Math.11(3) (1985) 209-222. · Zbl 0602.90136 |
| [14] | Briec, W. and Horvath, C., B-convexity, Optimization53 (2004) 103-127. · Zbl 1144.90506 |
| [15] | Butkovič, P. and MacCaig, M., On integer eigenvectors and subeigenvectors in the max-plus algebra, Linear Algebra Appl.438(8) (2013) 3408-3424. · Zbl 1267.15023 |
| [16] | M. Borman, The ranks of a tropical matrix, PhD thesis, Reed College (2007). |
| [17] | Butkovič, P., Max-Linear Systems: Theory and Algorithms, (Springer, London, 2010). · Zbl 1202.15032 |
| [18] | Brightwell, G. and Winkler, P., Counting linear extensions, Order8(3) (1991) 225-242. · Zbl 0759.06001 |
| [19] | Cohen, G., Gaubert, S. and Quadrat, J., Max-plus algebra and system theory: Where we are and where to go now, Ann. Rev. Control23 (1999) 207-219. |
| [20] | Cohen, G., Gaubert, S. and Quadrat, J.-P., Duality and separation theorems in idempotent semimodules, Linear Algebra Appl.379 (2004) 395-422. · Zbl 1042.46004 |
| [21] | Dyer, M. E. and Frieze, A. M., On the complexity of computing the volume of a polyhedron, SIAM J. Comput.17(5) (1988) 967-974. · Zbl 0668.68049 |
| [22] | Dyer, M., Frieze, A. and Kannan, R., A random polynomial-time algorithm for approximating the volume of convex bodies, J. Assoc. Comput. Mach.38(1) (1991) 1-17. · Zbl 0799.68107 |
| [23] | J. Depersin, S. Gaubert and J. Joswig, A tropical isoperimetric inequality, Sém. Loth. Combin.78B (2017) Article #27, 12 pp., Proceedings of FPSAC 2017 (29th Conference on Formal Power Series and Algebraic Combinatorics, London). · Zbl 1397.14077 |
| [24] | Dyer, M., Kannan, R. and Mount, J., Sampling contingency tables, Random Struct. Algorith.10(4) (1997) 487-506. · Zbl 0884.62065 |
| [25] | De Loera, J. A., The many aspects of counting lattice points in polytopes, Math. Sem.52(2) (2005) 175-195. · Zbl 1093.52006 |
| [26] | de la Puente, M. J., On tropical Kleene star matrices and alcoved polytopes, Kybernetika (Prague)49(6) (2013) 897-910. · Zbl 1297.15029 |
| [27] | De Loera, J. A. and Sturmfels, B., Algebraic unimodular counting, Math. Program.96(2, Ser. B) (2003) 183-203. · Zbl 1059.90105 |
| [28] | Develin, M. and Sturmfels, B., Tropical convexity, Doc. Math.9 (2004) 1-27 (electronic). · Zbl 1054.52004 |
| [29] | Develin, M., Santos, F. and Sturmfels, B., On the rank of a tropical matrix, in Combinatorial and Computational Geometry, , Vol. 52 (Cambridge Universtity Press, Cambridge, 2005), pp. 213-242. · Zbl 1095.15001 |
| [30] | Develin, M. and Yu, J., Tropical polytopes and cellular resolutions, Exp. Math.16(3) (2007). · Zbl 1134.52006 |
| [31] | Ehrhart, E., Sur les polyèdres rationnels homothétiques à \(n\) dimensions, C. R. Acad. Sci. Paris.254 (1962) 616-618. · Zbl 0100.27601 |
| [32] | Elekes, G., A geometric inequality and the complexity of computing volume, Discr. Comput. Geom.1(4) (1986) 289-292. · Zbl 0611.52010 |
| [33] | Garey, M. R. and Johnson, D. S., Computers and Intractability (W. H. Freeman and Co., San Francisco, Calif., 1979). . · Zbl 0411.68039 |
| [34] | Gritzmann, P. and Klee, V., On the complexity of some basic problems in computational convexity. II, Volume and mixed volumes, in Polytopes: Abstract, Convex and Computational (Scarborough, ON, 1993), , Vol. 440 (Kluwer Academic Publication, Dordrecht, 1994), pp. 373-466. · Zbl 0819.52008 |
| [35] | Grötschel, M., Lovász, L. and Schrijver, A., Geometric Algorithms and Combinatorial Optimization Algorithms and Combinatorics, Vol. 2 (Springer-Verlag, Berlin, 1993). · Zbl 0837.05001 |
| [36] | J. E. Goodman and J. O’Rourke eds., Handbook of Discrete and Computational Geometry, in Discrete Mathematics and its Applications (Boca Raton), 2nd edn. (Chapman & Hall/CRC, Boca Raton, FL, 2004). · Zbl 1056.52001 |
| [37] | Grigoriev, D. and Podolskii, V. V., Complexity of tropical and min-plus linear prevarieties, Comput. Complex.24(1) (2015) 31-64. · Zbl 1326.15039 |
| [38] | Henk, M., Richter-Gebert, J. and Ziegler, G. M., Basic properties of convex polytopes, in Handbook of Discrete and Computational Geometry, (CRC, Boca Raton, FL, 1997), pp. 243-270. · Zbl 0911.52007 |
| [39] | Izhakian, Z. and Rowen, L., The tropical rank of a tropical matrix, Comm. Algebra37(11) (2009) 3912-3927. · Zbl 1184.15003 |
| [40] | Joswig, M. and Kulas, K., Tropical and ordinary convexity combined, Adv. Geom.10(2) (2010) 333-352. · Zbl 1198.14060 |
| [41] | Joswig, M., Sturmfels, B. and Yu, J., Affine buildings and tropical convexity, Albanian J. Math.1(4) (2007) 187-211. · Zbl 1133.52003 |
| [42] | R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972) (Plenum, New York, 1972), pp. 85-103. · Zbl 1467.68065 |
| [43] | Katz, R. D., Max-plus (A,B)-invariant spaces and control of timed discrete event systems, IEEE Trans. Aut. Control52(2) (2007) 229-241. · Zbl 1366.93351 |
| [44] | K. Kim and F. Roush, Factorization of polynomials in one variable over the tropical semiring, arXiv:math/0501167, (2005). |
| [45] | Lam, T. and Postnikov, A., Alcoved polytopes I, Discr. Comput. Geom.38(3) (2007) 453-478. · Zbl 1134.52019 |
| [46] | T. Lam and A. Postnikov, Alcoved polytopes II, arXiv:1202.4015v1 (2012). · Zbl 1134.52019 |
| [47] | M. MacCaig, Integrality in max-linear systems, PhD thesis, The University of Birmingham (2015). · Zbl 1323.65067 |
| [48] | MacCaig, M., Exploring the complexity of the integer image problem in the max-algebra, Discr. Appl. Math.217(2) (2017) 261-275. · Zbl 1362.15022 |
| [49] | A. Miné, Weakly relational numerical abstract domains, PhD thesis, École Polytechnique, Palaiseau, France (2004). · Zbl 1126.68353 |
| [50] | Mount, J., Fast unimodular counting, Combin. Probab. Comput.9(3) (2000) 277-285. · Zbl 0973.90052 |
| [51] | Maclagan, D. and Sturmfels, B., Introduction to Tropical Geometry, , Vol. 161 (AMS, Providence, RI, 2015). · Zbl 1321.14048 |
| [52] | Möhring, R. H., Skutella, M. and Stork, F., Scheduling with AND/OR precedence constraints, SIAM J. Comput.33(2) (2004) 393-415. · Zbl 1112.90034 |
| [53] | Sergeev, S., Max-plus definite matrix closures and their eigenspaces, Linear Algebra Appl.421(2-3) (2007) 182-201. · Zbl 1131.15009 |
| [54] | Shilov, G. E., Linear Algebra, English edition (Dover Publications, Inc., New York, 1977). Translated from the Russian and edited by Silverman, Richard A.. · Zbl 0391.28007 |
| [55] | Shitov, Y., On the complexity of Boolean matrix ranks, Linear Algebra Appl.439(8) (2013) 2500-2502. · Zbl 1286.68209 |
| [56] | Stanley, R. P., Two poset polytopes, Discr. Comput. Geom.1 (1986) 9-23. · Zbl 0595.52008 |
| [57] | Werner, A. and Yu, J., Symmetric alcoved polytopes, Electron. J. Combin.21(1) (2014) Paper 1.20, 14. · Zbl 1302.52014 |
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.
