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 language | English |
|---|---|
| Title of host publication | Integer Programming and Combinatorial Optimization |
| Subtitle of host publication | 17th International Conference, IPCO 2014, Proceedings |
| Publisher | Springer |
| Pages | 309-320 |
| Number of pages | 12 |
| ISBN (Electronic) | 978-3-319-07557-0 |
| ISBN (Print) | 978-3-319-07556-3 |
| DOIs | |
| Publication status | Published - 1 Jan 2014 |
| Externally published | Yes |
| Event | 17th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2014 - University of Bonn, Bonn, Germany Duration: 23 Jun 2014 → 25 Jun 2014 Conference number: 17 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 8494 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 17th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2014 |
|---|---|
| Abbreviated title | IPCO 2014 |
| Country/Territory | Germany |
| City | Bonn |
| Period | 23/06/14 → 25/06/14 |