Tropical lower bound for extended formulations. II. Deficiency graphs of matrices
- Authors: Shitov Y.N.1
-
Affiliations:
- HSE University
- Issue: Vol 83, No 1 (2019)
- Pages: 203-216
- Section: Articles
- URL: https://ogarev-online.ru/1607-0046/article/view/133779
- DOI: https://doi.org/10.4213/im8698
- ID: 133779
Cite item
Open Access
Access granted
Subscription Access
Abstract
Deficiency graphs arise in the problem of decomposing a tropical vectorinto a sum of points of a given tropical variety.We give an application of this concept to the theory of extendedformulations of convex polytopes, and we show that the chromatic numberof the deficiency graph of a special tropical matrix is a lower boundfor the extension complexity of the corresponding convex polytope.We compare our new lower bound for extended formulations with existingestimates and make several conjectures on the relations betweendeficiency graphs, extended formulations, and rank functions of tropicalmatrices.
About the authors
Yaroslav Nikolaevich Shitov
HSE UniversityDoctor of physico-mathematical sciences, no status
References
- A. I. Barvinok, “Two algorithmic results for the traveling salesman problem”, Math. Oper. Res., 21:1 (1996), 65–84
- M. Develin, “Tropical secant varieties of linear spaces”, Discrete Comput. Geom., 35:1 (2006), 117–129
- 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
- Ya. Shitov, “Tropical lower bounds for extended formulations”, Math. Program., 153:1, Ser. B (2015), 67–74
- Э. Энгелер, Метаматематика элементарной математики, Мир, М., 1987, 128 с.
- F. J. Rayner, “Algebraically closed fields analogous to fields of Puiseux series”, J. London Math. Soc. (2), 8:3 (1974), 504–506
- M. Yannakakis, “Expressing combinatorial optimization problems by linear programs”, J. Comput. System Sci., 43:3 (1991), 441–466
- 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
- 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
- N. Gillis, F. Glineur, “On the geometric interpretation of the nonnegative rank”, Linear Algebra Appl., 437:11 (2012), 2685–2712
- S. Fiorini, T. Rothvoss, H. R. Tiwary, “Extended formulations for polygons”, Discrete Comput. Geom., 48:3 (2012), 658–668
- А. В. Рязанов, Оценки неотрицательных и полуопределенных рангов матриц, Доклад в рамках молодежной школы “Управление, информация и оптимизация”, М., 2017
- Я. Н. Шитов, Линейная алгебра над полукольцами, Дисс. … докт. физ.-матем. наук, МГУ им. М. В. Ломоносова, М., 2015, 302 с.
- J. Gouveia, R. Z. Robinson, R. R. Thomas, “Polytopes of minimum positive semidefinite rank”, Discrete Comput. Geom., 50:3 (2013), 679–699
- S. Fiorini, V. Kaibel, K. Pashkovich, D. O. Theis, “Combinatorial bounds on nonnegative rank and extended formulations”, Discrete Math., 313:1 (2013), 67–83
- Ya. Shitov, “The complexity of tropical matrix factorization”, Adv. Math., 254 (2014), 138–156
- D. Cartwright, M. Chan, “Three notions of tropical rank for symmetric matrices”, Combinatorica, 32:1 (2012), 55–84
- М. Гэри, Д. Джонсон, Вычислительные машины и труднорешаемые задачи, Мир, М., 1982, 416 с.
- E. L. Lawler, “A note on the complexity of the chromatic number problem”, Information Processing Lett., 5:3 (1976), 66–67
- Ya. Shitov, “Detecting matrices of combinatorial rank three”, J. Combin. Theory Ser. A, 126 (2014), 166–176
- Н. К. Верещагин, Лекции по теории информации, 158 с.
- L. B. Beasley, “Isolation number versus Boolean rank”, Linear Algebra Appl., 436:9 (2012), 3469–3474
- Ya. Shitov, “Mixtures of star trees and deficiency graphs”, European J. Combin., 44, Part A (2015), 140–143
- J. Culberson, I. Gent, “Frozen development in graph coloring”, Theoret. Comput. Sci., 265:1-2 (2001), 227–264
- J. Gouveia, P. A. Parrilo, R. R. Thomas, “Lifts of convex sets and cone factorizations”, Math. Oper. Res., 38:2 (2013), 248–264
- Ya. Shitov, “Studying non-negative factorizations with tools from linear algebra over a semiring”, Comm. Algebra, 43:10 (2015), 4359–4366
- A. Padrol, J. Pfeifle, “Polygons as sections of higher-dimensional polytopes”, Electron. J. Combin., 22:1 (2015), 1.24, 16 pp.
- K. Pashkovich, S. Weltge, “Hidden vertices in extensions of polytopes”, Oper. Res. Lett., 43:2 (2015), 161–164
- Ya. Shitov, “An upper bound for nonnegative rank”, J. Combin. Theory Ser. A, 122 (2014), 126–132
- A. Vandaele, N. Gillis, F. Glineur, D. Tuyttens, “Heuristics for exact nonnegative matrix factorization”, J. Global Optim., 65:2 (2016), 369–400
- A. Padrol, “Extension complexity of polytopes with few vertices or facets”, SIAM J. Discrete Math., 30:4 (2016), 2162–2176
- Ya. Shitov, Sublinear extensions of polygons
- Я. Н. Шитов, “О булевых матрицах полного факторизационного ранга”, Матем. сб., 204:11 (2013), 151–160
- Ya. Shitov, A separation between tropical matrix ranks
Supplementary files
