On Permuting Some Coordinates of Polytopes

Result code in 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>

Result on the web

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

Result language

angličtina

Original language name

On Permuting Some Coordinates of Polytopes

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2022

Confidentiality

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

Article name in the collection

COMBINATORIAL OPTIMIZATION (ISCO 2022)

ISBN

978-3-031-18529-8

ISSN

0302-9743

e-ISSN

1611-3349

Number of pages

13

Pages from-to

102-114

Publisher name

SPRINGER INTERNATIONAL PUBLISHING AG

Place of publication

CHAM

Event location

Online

Event date

May 18, 2022

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000897756400008