Simple extensions of polytopes

Volker Kaibel, Matthias Walter

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)

Abstract

We introduce the simple extension complexity of a polytope P as the smallest number of facets of any simple (i.e., non-degenerate in the sense of linear programming) polytope which can be projected onto P. We devise a combinatorial method to establish lower bounds on the simple extension complexity and show for several polytopes that they have large simple extension complexities. These examples include both the spanning tree and the perfect matching polytopes of complete graphs, uncapacitated flow polytopes for non-trivially decomposable directed acyclic graphs, and random 0/1-polytopes with vertex numbers within a certain range. On our way to obtain the result on perfect matching polytopes we improve on a result of Padberg and Rao's on the adjacency structures of those polytopes.

Original languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization
Subtitle of host publication17th International Conference, IPCO 2014, Proceedings
PublisherSpringer Verlag
Pages309-320
Number of pages12
ISBN (Electronic)978-3-319-07557-0
ISBN (Print)978-3-319-07556-3
DOIs
Publication statusPublished - 1 Jan 2014
Externally publishedYes
Event17th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2014 - University of Bonn, Bonn, Germany
Duration: 23 Jun 201425 Jun 2014
Conference number: 17

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8494 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference17th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2014
Abbreviated titleIPCO 2014
CountryGermany
CityBonn
Period23/06/1425/06/14

Fingerprint Dive into the research topics of 'Simple extensions of polytopes'. Together they form a unique fingerprint.

  • Cite this

    Kaibel, V., & Walter, M. (2014). Simple extensions of polytopes. In Integer Programming and Combinatorial Optimization: 17th International Conference, IPCO 2014, Proceedings (pp. 309-320). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8494 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-07557-0_26