On Permuting Some Coordinates of Polytopes

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10455819" target="_blank" >RIV/00216208:11320/22:10455819 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-031-18530-4_8" target="_blank" >https://doi.org/10.1007/978-3-031-18530-4_8</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-18530-4_8" target="_blank" >10.1007/978-3-031-18530-4_8</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On Permuting Some Coordinates of Polytopes

Popis výsledku v původním jazyce

Let P subset of R-d be a polytope with coordinates labeled x(1),..., x(d). Define perm(I)(P) to be the polytope obtained by taking every permutation sigma whose set of fixed-points is [d] I, permuting the coordinates of every point in P according to sigma and taking the convex hull of all such points. Also, define sort(P) to be the polytope obtained by taking each vertex of P in &quot;sorted order&quot;. In this article we study the extension complexity of perm(I)(P) and sort(P) in terms of the extension complexity of P. A result by Kaibel and Pashkovich states that if sort(P) subset of P and I = [d] then the extension complexity of perm(I)(P) is bounded above by a polynomial of the extension complexity of P. We show that the extension complexity of permI (P) can increase exponentially if I not equal [d] even if the vertices of P contain only three values, say 0, 1, or 2 at each of the coordinates xi for i is an element of I. Furthermore, the extension complexity of sort(P) can be exponentially larger than that of P. We also discuss the implications for the 0/1 case.

Název v anglickém jazyce

On Permuting Some Coordinates of Polytopes

Popis výsledku anglicky

Let P subset of R-d be a polytope with coordinates labeled x(1),..., x(d). Define perm(I)(P) to be the polytope obtained by taking every permutation sigma whose set of fixed-points is [d] I, permuting the coordinates of every point in P according to sigma and taking the convex hull of all such points. Also, define sort(P) to be the polytope obtained by taking each vertex of P in &quot;sorted order&quot;. In this article we study the extension complexity of perm(I)(P) and sort(P) in terms of the extension complexity of P. A result by Kaibel and Pashkovich states that if sort(P) subset of P and I = [d] then the extension complexity of perm(I)(P) is bounded above by a polynomial of the extension complexity of P. We show that the extension complexity of permI (P) can increase exponentially if I not equal [d] even if the vertices of P contain only three values, say 0, 1, or 2 at each of the coordinates xi for i is an element of I. Furthermore, the extension complexity of sort(P) can be exponentially larger than that of P. We also discuss the implications for the 0/1 case.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

COMBINATORIAL OPTIMIZATION (ISCO 2022)

ISBN

978-3-031-18529-8

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

13

Strana od-do

102-114

Název nakladatele

SPRINGER INTERNATIONAL PUBLISHING AG

Místo vydání

CHAM

Místo konání akce

Online

Datum konání akce

18. 5. 2022

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000897756400008