Tropical lower bounds for extended formulations

Yaroslav Shitov

doi:10.1007/s10107-014-0833-6

Публикации

?

Tropical lower bounds for extended formulations

Mathematical Programming. 2015. Vol. 153. No. 1. P. 67–74.

Yaroslav Shitov

The tropical arithmetic operations on R arise from studying the geometry over non-Archimedean fields. We present an application of tropical methods to the study of extended formulations for convex polytopes. We propose a non-Archimedean generalization of the well known Boolean rank bound for the extension complexity. We show how to construct a real polytope with the same extension complexity and combinatorial type as a given non-Archimedean polytope. Our results allow us to develop a method of constructing real polytopes with large extension complexity.

Приоритетные направления: компьютерно-математическое математика

Язык: английский

Полный текст

DOI

Текст на другом сайте

Ключевые слова: Tropical matrices convex polytope extended formulation

ML-based Fast Simulation of FARICH Responses

Шипилов Ф. А., Barnyakov A., Ivanov A. и др., / Series Physics "arxiv.org". 2026.

Добавлено: 19 мая 2026 г.

Bifurcations and Structural Stability of Generic PC-HC Families

Доровский А. А., / Series arXiv "math". 2026.

Добавлено: 14 мая 2026 г.

On the minimum number of maximal distance-k independent sets in trees

Талецкий Д. С., / Series arXiv "math". 2026.

Добавлено: 1 мая 2026 г.

On Arithmetic Mirror Symmetry for smooth Fano fourfolds

Овчаренко М. А., / Series arXiv "math". 2026.

Добавлено: 30 апреля 2026 г.

Natural hazard database from Internet publications: text mining with a large language model

Деркачева А. А., Сакиркина М. А., Краев Г. Н. и др., /. 2026.

Добавлено: 28 апреля 2026 г.

Ising models on the hydrogen peroxide and other lattices

Qin X., Deng Y., Щур Л. Н. и др., / Series arXiv "math". 2026. No. 2603.02962.

Добавлено: 20 апреля 2026 г.

Algorithmic overlaps as thermodynamic variables: from local to cluster Monte Carlo dynamics in critical phenomena

Пиле Я. Э., Deng Y., Щур Л. Н., / Series arXiv "math". 2026. No. 2604.10254.

Добавлено: 20 апреля 2026 г.

On weak solutions to the 1d compressible Navier-Stokes equations: a Lipschitz continuous dependence on data in weaker norms and an error of their homogenization

Zlotnik Alexander, / Series arXiv "math". 2026. No. 2602.03481v1.

Добавлено: 18 апреля 2026 г.

On the dimension of the space of static potentials on three-manifolds

Медведев В. О., / Series arXiv "math". 2026.

We investigate the interplay between the dimension of the space of static potentials and the geometric and topological structure of the underlying static three-manifold. A partial classification of boundaryless static manifolds is obtained in terms of this dimension. We also treat the case of static manifolds with boundary. In particular, we prove that if a ...

Добавлено: 3 апреля 2026 г.

Using predefined vector systems to speed up neural network multimillion class classification

Gabdullin N., Андросов И. А., / Series Computer Science "arxiv.org". 2026.

Добавлено: 2 апреля 2026 г.

Homogeneous maximizers of the Blaschke-Santalo-type functionals

Колесников А. В., / Series arXiv "math". 2025.

Добавлено: 13 февраля 2026 г.

Iterative Ricci-Foster Curvature Flow with GMM-Based Edge Pruning: A Novel Approach to Community Detection

Сорокин К. С., Бекетов М. Е., Онучин А. и др., / arxiv.org. Серия cs.SI "Social and Information Networks ". 2025.

Обнаружение сообществ в сложных сетях — фундаментальная проблема, открытая для новых подходов в различных научных областях. Мы представляем новый метод обнаружения сообществ, основанный на потоке Риччи на графах. Наша техника итеративно обновляет веса ребер (их метрические длины) в соответствии с их (комбинаторной) версией кривизны Риччи Фостера, вычисленной на основе эффективного расстояния сопротивления между узлами. Известно, ...

Добавлено: 15 января 2026 г.

Теория семейств многогранников: фуллерены и многогранники А. В. Погорелова

Ероховец Н. Ю., Вестник Московского университета. Серия 1: Математика. Механика 2021 № 2 С. 61–72

Статья представляет собой обзор результатов одноименного цикла работ автора, отмеченного премией имени И. И. Шувалова 2018 года за научную деятельность I степени, и более поздних результатов. В ней изучаются семейства трехмерных простых многогранников, определяемые условием циклической k-реберной связности, в частности флаговые многогранники и многогранники А. В. Погорелова, а также связанные с ними семейства фуллеренов и идеальных прямоугольных гиперболических многогранников. Описаны ...

Добавлено: 26 ноября 2025 г.

Каноническая геометризация ориентируемых трехмерных многообразий, определяемых векторными раскрасками трехмерных многогранников

Ероховец Н. Ю., Математический сборник 2022 Т. 213 № 6 С. 21–70

Гипотеза У. П. Тёрстона о геометризации (окончательно доказанная Г. Я. Перельманом) заключается в том, что любое ориентируемое трехмерное многообразие может быть канонически разрезано на части, каждая из которых имеет геометрическую структуру, моделируемую на одной из восьми геометрий: S^3, R^3, H^3, S^2×R, H^2×R, универсальное накрытие для SL(2,R), Nil и Sol. В фундаментальной работе 1991 г. М. Дэвис и Т. Янушкевич ввели широкий класс n-мерных многообразий – так называемые малые накрытия простых n-мерных многогранников. Мы даем полный ответ ...

Добавлено: 26 ноября 2025 г.

Spectral clustering of combinatorial fullerene isomers based on their facet graph structure

Bille A., Victor Buchstaber, Spodarev E., Journal of Mathematical Chemistry 2021 Vol. 59 No. 1 P. 264–288

Добавлено: 16 июня 2021 г.

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

Шитов Я. Н., Izvestiya. Mathematics 2019 Vol. 83 No. 1 P. 184–195

Добавлено: 11 ноября 2020 г.

An upper bound for a valence of a face in a parallelohedral tiling

Magazinov A., European Journal of Combinatorics 2013 Vol. 34 No. 7 P. 1108–1113

Добавлено: 4 октября 2018 г.

Extended formulations for convex heptagons

Шитов Я. Н., Доклады Академии наук 2015 Vol. 92 No. 3 P. 707–708

Results related to extended formulations of convex polygons are discussed. In particular, it turns out that six linear inequalities are sufficient to describe a convex heptagon up to a linear projection. ...

Добавлено: 23 февраля 2016 г.

On integer programming with bounded determinants

Грибанов Д. В., Veselov S. I., Optimization Letters 2016 Vol. 10 No. 6 P. 1169–1177

Добавлено: 12 октября 2015 г.

Rank functions of tropical matrices

Alexander Guterman, Yaroslav Shitov, Linear Algebra and its Applications 2016 Vol. 498 P. 326–348

Добавлено: 10 августа 2015 г.

On matrices with different tropical and Kapranov ranks

Шитов Я. Н., Mathematical notes 2012 Vol. 92 No. 2 P. 286–291

Добавлено: 20 января 2014 г.

Matrices with different Gondran-Minoux and determinantal ranks over max-algebras

Шитов Я. Н., Journal of Mathematical Sciences 2009 Vol. 163 No. 5 P. 598–624

Добавлено: 20 января 2014 г.

An upper bound for nonnegative rank

Yaroslav Shitov, Journal of Combinatorial Theory, Series A 2014 Vol. 122 P. 126–132

We provide a nontrivial upper bound for the nonnegative rank of rank-three matrices which allows us to prove that [6(n+1)/7] linear inequalities suffice to describe a convex n-gon up to a linear projection. ...

Добавлено: 8 ноября 2013 г.

Aleksandrov-Fenchel inequality for coconvex bodies

Тиморин В. А., Khovanskii A. G., / Series math "arxiv.org". 2013. No. 1305.4484.

Добавлено: 6 октября 2013 г.