On the notions of facets, weak facets, and extreme functions of the gomory–johnson infinite group problem

Matthias Köppe; Yuan Zhou

doi:10.1007/978-3-319-59250-3_27

On the notions of facets, weak facets, and extreme functions of the gomory–johnson infinite group problem

Matthias Köppe, Yuan Zhou

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Scopus citations

Abstract

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.

Original language	English
Title of host publication	Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings
Editors	Friedrich Eisenbrand, Jochen Koenemann
Pages	330-342
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-319-59250-3_27
State	Published - 2017
Event	19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017 - Waterloo, Canada Duration: Jun 26 2017 → Jun 28 2017

Publication series

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

Conference

Conference	19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017
Country/Territory	Canada
City	Waterloo
Period	6/26/17 → 6/28/17

Bibliographical note

Publisher Copyright:
© Springer International Publishing AG 2017.

Funding

The authors gratefully acknowledge partial support from the National Science Foundation through grant DMS-1320051, awarded to M. Köppe.

Funders	Funder number
National Science Foundation (NSF)	DMS-1320051
Directorate for Mathematical and Physical Sciences	1320051

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-59250-3_27

Cite this

Köppe, M., & Zhou, Y. (2017). On the notions of facets, weak facets, and extreme functions of the gomory–johnson infinite group problem. In F. Eisenbrand, & J. Koenemann (Eds.), Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings (pp. 330-342). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10328 LNCS). https://doi.org/10.1007/978-3-319-59250-3_27

Köppe, Matthias ; Zhou, Yuan. / On the notions of facets, weak facets, and extreme functions of the gomory–johnson infinite group problem. Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings. editor / Friedrich Eisenbrand ; Jochen Koenemann. 2017. pp. 330-342 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{914c70ba78224312b95706024b2df912,

title = "On the notions of facets, weak facets, and extreme functions of the gomory–johnson infinite group problem",

abstract = "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.",

author = "Matthias K{\"o}ppe and Yuan Zhou",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017 ; Conference date: 26-06-2017 Through 28-06-2017",

year = "2017",

doi = "10.1007/978-3-319-59250-3_27",

language = "English",

isbn = "9783319592497",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "330--342",

editor = "Friedrich Eisenbrand and Jochen Koenemann",

booktitle = "Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings",

}

Köppe, M & Zhou, Y 2017, On the notions of facets, weak facets, and extreme functions of the gomory–johnson infinite group problem. in F Eisenbrand & J Koenemann (eds), Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10328 LNCS, pp. 330-342, 19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017, Waterloo, Canada, 6/26/17. https://doi.org/10.1007/978-3-319-59250-3_27

On the notions of facets, weak facets, and extreme functions of the gomory–johnson infinite group problem. / Köppe, Matthias; Zhou, Yuan.
Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings. ed. / Friedrich Eisenbrand; Jochen Koenemann. 2017. p. 330-342 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10328 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On the notions of facets, weak facets, and extreme functions of the gomory–johnson infinite group problem

AU - Köppe, Matthias

AU - Zhou, Yuan

PY - 2017

Y1 - 2017

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

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

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

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

U2 - 10.1007/978-3-319-59250-3_27

DO - 10.1007/978-3-319-59250-3_27

M3 - Conference contribution

AN - SCOPUS:85020528023

SN - 9783319592497

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

SP - 330

EP - 342

BT - Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings

A2 - Eisenbrand, Friedrich

A2 - Koenemann, Jochen

T2 - 19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017

Y2 - 26 June 2017 through 28 June 2017

ER -

Köppe M, Zhou Y. On the notions of facets, weak facets, and extreme functions of the gomory–johnson infinite group problem. In Eisenbrand F, Koenemann J, editors, Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings. 2017. p. 330-342. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-59250-3_27

On the notions of facets, weak facets, and extreme functions of the gomory–johnson infinite group problem

Abstract

Publication series

Conference

Bibliographical note

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this