Tropical lower bound for extended formulations. II. Deficiency graphs of matrices

Ya. Shitov

Izvestiya. Mathematics , Tome 83 (2019) no. 1, pp. 184-195.

Résumé

Deficiency graphs arise in the problem of decomposing a tropical vector into a sum of points of a given tropical variety. We give an application of this concept to the theory of extended formulations of convex polytopes, and we show that the chromatic number of the deficiency graph of a special tropical matrix is a lower bound for the extension complexity of the corresponding convex polytope. We compare our new lower bound for extended formulations with existing estimates and make several conjectures on the relations between deficiency graphs, extended formulations, and rank functions of tropical matrices.

Détail

Keywords: convex polytope, extended formulation, tropical mathematics.

Bibliographie

[1] A. I. Barvinok, “Two algorithmic results for the traveling salesman problem”, Math. Oper. Res., 21:1 (1996), 65–84 | DOI | MR | Zbl

[2] M. Develin, “Tropical secant varieties of linear spaces”, Discrete Comput. Geom., 35:1 (2006), 117–129 | DOI | MR | Zbl

[3] M. Develin, F. Santos, B. Sturmfels, “On the rank of a tropical matrix”, Combinatorial and computational geometry, Math. Sci. Res. Inst. Publ., 52, Cambridge Univ. Press, Cambridge, 2005, 213–242 | MR | Zbl

[4] Ya. Shitov, “Tropical lower bounds for extended formulations”, Math. Program., 153:1, Ser. B (2015), 67–74 | DOI | MR | Zbl

[5] E. Engeler, Metamathematik der Elementarmathematik, Hochschultext, Springer-Verlag, Berlin, 1983, ii+132 pp. | DOI | MR | MR | Zbl | Zbl

[6] F. J. Rayner, “Algebraically closed fields analogous to fields of Puiseux series”, J. London Math. Soc. (2), 8:3 (1974), 504–506 | DOI | MR | Zbl

[7] M. Yannakakis, “Expressing combinatorial optimization problems by linear programs”, J. Comput. System Sci., 43:3 (1991), 441–466 | DOI | MR | Zbl

[8] S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, R. de Wolf, “Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds”, STOC '12 Proceedings of the 44th annual ACM symposium on theory of computing, ACM, New York, 2012, 95–106 | DOI | MR | Zbl

[9] T. Rothvoss, “The matching polytope has exponential extension complexity”, STOC '14 Proceedings of the 46th annual ACM symposium on theory of computing, ACM, New York, 2014, 263–272 | DOI | MR | Zbl

[10] N. Gillis, F. Glineur, “On the geometric interpretation of the nonnegative rank”, Linear Algebra Appl., 437:11 (2012), 2685–2712 | DOI | MR | Zbl

[11] S. Fiorini, T. Rothvoß, H. R. Tiwary, “Extended formulations for polygons”, Discrete Comput. Geom., 48:3 (2012), 658–668 | DOI | MR | Zbl

[12] A. V. Ryazanov, Otsenki neotritsatelnykh i poluopredelennykh rangov matrits, Doklad v ramkakh molodezhnoi shkoly “Upravlenie, informatsiya i optimizatsiya”, M., 2017

[13] Ya. N. Shitov, Lineinaya algebra nad polukoltsami, Diss. ... dokt. fiz.-matem. nauk, MGU im. M. V. Lomonosova, M., 2015, 302 pp.

[14] J. Gouveia, R. Z. Robinson, R. R. Thomas, “Polytopes of minimum positive semidefinite rank”, Discrete Comput. Geom., 50:3 (2013), 679–699 | DOI | MR | Zbl

[15] S. Fiorini, V. Kaibel, K. Pashkovich, D. O. Theis, “Combinatorial bounds on nonnegative rank and extended formulations”, Discrete Math., 313:1 (2013), 67–83 | DOI | MR | Zbl

[16] Ya. Shitov, “The complexity of tropical matrix factorization”, Adv. Math., 254 (2014), 138–156 | DOI | MR | Zbl

[17] D. Cartwright, M. Chan, “Three notions of tropical rank for symmetric matrices”, Combinatorica, 32:1 (2012), 55–84 | DOI | MR | Zbl

[18] M. R. Garey, D. S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, Ser. Books Math. Sci., W. H. Freeman and Co., San Francisco, Calif., 1979, x+338 pp. | MR | MR | Zbl | Zbl

[19] E. L. Lawler, “A note on the complexity of the chromatic number problem”, Information Processing Lett., 5:3 (1976), 66–67 | DOI | MR | Zbl

[20] Ya. Shitov, “Detecting matrices of combinatorial rank three”, J. Combin. Theory Ser. A, 126 (2014), 166–176 | DOI | MR | Zbl

[21] N. K. Vereschagin, Lektsii po teorii informatsii, 158 pp. https://docplayer.ru/53661662-Lekcii-po-teorii-informacii-n-k-vereshchagin.html

[22] L. B. Beasley, “Isolation number versus Boolean rank”, Linear Algebra Appl., 436:9 (2012), 3469–3474 | DOI | MR | Zbl

[23] Ya. Shitov, “Mixtures of star trees and deficiency graphs”, European J. Combin., 44, Part A (2015), 140–143 | DOI | MR | Zbl

[24] J. Culberson, I. Gent, “Frozen development in graph coloring”, Theoret. Comput. Sci., 265:1-2 (2001), 227–264 | DOI | MR | Zbl

[25] J. Gouveia, P. A. Parrilo, R. R. Thomas, “Lifts of convex sets and cone factorizations”, Math. Oper. Res., 38:2 (2013), 248–264 | DOI | MR | Zbl

[26] Ya. Shitov, “Studying non-negative factorizations with tools from linear algebra over a semiring”, Comm. Algebra, 43:10 (2015), 4359–4366 | DOI | MR | Zbl

[27] A. Padrol, J. Pfeifle, “Polygons as sections of higher-dimensional polytopes”, Electron. J. Combin., 22:1 (2015), 1.24, 16 pp. | MR | Zbl

[28] K. Pashkovich, S. Weltge, “Hidden vertices in extensions of polytopes”, Oper. Res. Lett., 43:2 (2015), 161–164 | DOI | MR | Zbl

[29] Ya. Shitov, “An upper bound for nonnegative rank”, J. Combin. Theory Ser. A, 122 (2014), 126–132 | DOI | MR | Zbl

[30] A. Vandaele, N. Gillis, F. Glineur, D. Tuyttens, “Heuristics for exact nonnegative matrix factorization”, J. Global Optim., 65:2 (2016), 369–400 ; arXiv: 1411.7245 | DOI | MR | Zbl

[31] A. Padrol, “Extension complexity of polytopes with few vertices or facets”, SIAM J. Discrete Math., 30:4 (2016), 2162–2176 ; arXiv: 1602.06894 | DOI | MR | Zbl

[32] Ya. Shitov, Sublinear extensions of polygons, arXiv: 1412.0728

[33] Ya. Shitov, “On Boolean matrices with full factor rank”, Sb. Math., 204:11 (2013), 1691–1699 | DOI | DOI | MR | Zbl

[34] Ya. Shitov, A separation between tropical matrix ranks, arXiv: 1712.03071