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
Abstract
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
