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

Copyright (c) 2019 Shitov Y.N.

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

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