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

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access 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 University

Doctor of physico-mathematical sciences, no status

References

  1. A. I. Barvinok, “Two algorithmic results for the traveling salesman problem”, Math. Oper. Res., 21:1 (1996), 65–84
  2. M. Develin, “Tropical secant varieties of linear spaces”, Discrete Comput. Geom., 35:1 (2006), 117–129
  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
  4. Ya. Shitov, “Tropical lower bounds for extended formulations”, Math. Program., 153:1, Ser. B (2015), 67–74
  5. Э. Энгелер, Метаматематика элементарной математики, Мир, М., 1987, 128 с.
  6. F. J. Rayner, “Algebraically closed fields analogous to fields of Puiseux series”, J. London Math. Soc. (2), 8:3 (1974), 504–506
  7. M. Yannakakis, “Expressing combinatorial optimization problems by linear programs”, J. Comput. System Sci., 43:3 (1991), 441–466
  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
  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
  10. N. Gillis, F. Glineur, “On the geometric interpretation of the nonnegative rank”, Linear Algebra Appl., 437:11 (2012), 2685–2712
  11. S. Fiorini, T. Rothvoss, H. R. Tiwary, “Extended formulations for polygons”, Discrete Comput. Geom., 48:3 (2012), 658–668
  12. А. В. Рязанов, Оценки неотрицательных и полуопределенных рангов матриц, Доклад в рамках молодежной школы “Управление, информация и оптимизация”, М., 2017
  13. Я. Н. Шитов, Линейная алгебра над полукольцами, Дисс. … докт. физ.-матем. наук, МГУ им. М. В. Ломоносова, М., 2015, 302 с.
  14. J. Gouveia, R. Z. Robinson, R. R. Thomas, “Polytopes of minimum positive semidefinite rank”, Discrete Comput. Geom., 50:3 (2013), 679–699
  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
  16. Ya. Shitov, “The complexity of tropical matrix factorization”, Adv. Math., 254 (2014), 138–156
  17. D. Cartwright, M. Chan, “Three notions of tropical rank for symmetric matrices”, Combinatorica, 32:1 (2012), 55–84
  18. М. Гэри, Д. Джонсон, Вычислительные машины и труднорешаемые задачи, Мир, М., 1982, 416 с.
  19. E. L. Lawler, “A note on the complexity of the chromatic number problem”, Information Processing Lett., 5:3 (1976), 66–67
  20. Ya. Shitov, “Detecting matrices of combinatorial rank three”, J. Combin. Theory Ser. A, 126 (2014), 166–176
  21. Н. К. Верещагин, Лекции по теории информации, 158 с.
  22. L. B. Beasley, “Isolation number versus Boolean rank”, Linear Algebra Appl., 436:9 (2012), 3469–3474
  23. Ya. Shitov, “Mixtures of star trees and deficiency graphs”, European J. Combin., 44, Part A (2015), 140–143
  24. J. Culberson, I. Gent, “Frozen development in graph coloring”, Theoret. Comput. Sci., 265:1-2 (2001), 227–264
  25. J. Gouveia, P. A. Parrilo, R. R. Thomas, “Lifts of convex sets and cone factorizations”, Math. Oper. Res., 38:2 (2013), 248–264
  26. Ya. Shitov, “Studying non-negative factorizations with tools from linear algebra over a semiring”, Comm. Algebra, 43:10 (2015), 4359–4366
  27. A. Padrol, J. Pfeifle, “Polygons as sections of higher-dimensional polytopes”, Electron. J. Combin., 22:1 (2015), 1.24, 16 pp.
  28. K. Pashkovich, S. Weltge, “Hidden vertices in extensions of polytopes”, Oper. Res. Lett., 43:2 (2015), 161–164
  29. Ya. Shitov, “An upper bound for nonnegative rank”, J. Combin. Theory Ser. A, 122 (2014), 126–132
  30. A. Vandaele, N. Gillis, F. Glineur, D. Tuyttens, “Heuristics for exact nonnegative matrix factorization”, J. Global Optim., 65:2 (2016), 369–400
  31. A. Padrol, “Extension complexity of polytopes with few vertices or facets”, SIAM J. Discrete Math., 30:4 (2016), 2162–2176
  32. Ya. Shitov, Sublinear extensions of polygons
  33. Я. Н. Шитов, “О булевых матрицах полного факторизационного ранга”, Матем. сб., 204:11 (2013), 151–160
  34. Ya. Shitov, A separation between tropical matrix ranks

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2019 Shitov Y.N.

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).