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

Flow graphs
Polytopes
Linear programming
Perfect Matching
Polytope
Directed Acyclic Graph
Adjacency
Decomposable
Spanning tree
Facet
Complete Graph
Lower bound
Vertex of a graph
Range of data

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
Kaibel, Volker ; Walter, Matthias. / Simple extensions of polytopes. Integer Programming and Combinatorial Optimization: 17th International Conference, IPCO 2014, Proceedings. Springer Verlag, 2014. pp. 309-320 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{0424ae0effda4e4fbd8b0c3098c82caa,
title = "Simple extensions of polytopes",
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.",
author = "Volker Kaibel and Matthias Walter",
year = "2014",
month = "1",
day = "1",
doi = "10.1007/978-3-319-07557-0_26",
language = "English",
isbn = "978-3-319-07556-3",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "309--320",
booktitle = "Integer Programming and Combinatorial Optimization",
address = "Germany",

}

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

Simple extensions of polytopes. / Kaibel, Volker; Walter, Matthias.

Integer Programming and Combinatorial Optimization: 17th International Conference, IPCO 2014, Proceedings. Springer Verlag, 2014. p. 309-320 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8494 LNCS).

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

TY - GEN

T1 - Simple extensions of polytopes

AU - Kaibel, Volker

AU - Walter, Matthias

PY - 2014/1/1

Y1 - 2014/1/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=84958552070&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-07557-0_26

DO - 10.1007/978-3-319-07557-0_26

M3 - Conference contribution

SN - 978-3-319-07556-3

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 309

EP - 320

BT - Integer Programming and Combinatorial Optimization

PB - Springer Verlag

ER -

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