We investigate three competing notions that generalize the notion of a facet of finite-dimensional polyhedra to the infinite-dimensional Gomory–Johnson model. These notions were known to coincide for continuous piecewise linear functions with rational breakpoints. We show that two of the notions, extreme functions and facets, coincide for the case of continuous piecewise linear functions, removing the hypothesis regarding rational breakpoints. We then separate the three notions using discontinuous examples.
|Title of host publication||Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings|
|Editors||Friedrich Eisenbrand, Jochen Koenemann|
|Number of pages||13|
|State||Published - 2017|
|Event||19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017 - Waterloo, Canada|
Duration: Jun 26 2017 → Jun 28 2017
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017|
|Period||6/26/17 → 6/28/17|
Bibliographical noteFunding Information:
The authors gratefully acknowledge partial support from the National Science Foundation through grant DMS-1320051, awarded to M. Köppe.
© Springer International Publishing AG 2017.
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science (all)