Small extended formulations for cyclic polytopes (Q2351019): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / author | |||
Property / author: Aleksandr N. Maksimenko / rank | |||
Property / reviewed by | |||
Property / reviewed by: Alexander Esterov / rank | |||
Property / author | |||
Property / author: Aleksandr N. Maksimenko / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Alexander Esterov / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W3101583628 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1401.8138 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Combinatorial bounds on nonnegative rank and extended formulations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Extended formulations for polygons / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4434671 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Constructing Extended Formulations from Reflection Relations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Expressing combinatorial optimization problems by linear programs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Lectures on Polytopes / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 09:58, 10 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Small extended formulations for cyclic polytopes |
scientific article |
Statements
Small extended formulations for cyclic polytopes (English)
0 references
26 June 2015
0 references
The extension complexity of a convex polytope P is the minimal number of linear inequalities describing a polytope that projects to P, i.e. the minimal number of facets of such a polytope. In general, the extension complexity of P may be much less that the number of facets of P itself. See [\textit{M. Yannakakis}, J. Comput. Syst. Sci. 43, No. 3, 441--466 (1991; Zbl 0748.90074)] for a linear-algebraic reformulation of this notion. The main result of the present paper is as follows: the extension complexity of the d-dimensional cyclic polytope with \(n\) vertices does not exceed \(O(\log n)^{\lfloor d/2 \rfloor}\). For cyclic polygons, the proof is based on an explicit construction of a covering polytope with few facets. For arbitrary dimension, the proof is less straightforward and is based on the aforementioned algebraic reformulation of the extension complexity.
0 references
polytope extension
0 references
cyclic polytope
0 references
nonnegative factorization
0 references