0/1-integer programming: Optimization and augmentation are equivalent

Andreas S. Schulz; Robert Weismantel; Günter M. Ziegler

doi:10.1007/3-540-60313-1_164

0/1-integer programming: Optimization and augmentation are equivalent

Andreas S. Schulz, Robert Weismantel, Günter M. Ziegler

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

39 Scopus citations

Abstract

For every family of sets F ⊆ {0, 1}ⁿ the following problems are strongly polynomial time equivalent: given a feasible point x⁰ ϵ F and a linear objective function c ϵ ℤⁿ, find a feasible point x* ϵ F that maximizes cx (Optimization), _9 find a feasible point x^new ϵ F with cx^new > cx⁰ (Augmentation), and find a feasible point x^new ϵ F with c x^new > c x⁰ such that x^new—x⁰is “irreducible” (Irreducible Augmentation). This generalizes results and techniques that are well known for 0/1- integer programming problems that arise from various classes of combinatorial optimization problems.

Original language	English
Title of host publication	Algorithms - ESA 1995 - 3rd Annual European Symposium, Proceedings
Editors	Paul Spirakis
Publisher	Springer Verlag
Pages	473-483
Number of pages	11
ISBN (Print)	3540603131, 9783540603139
DOIs	https://doi.org/10.1007/3-540-60313-1_164
State	Published - 1995
Externally published	Yes
Event	3rd Annual European Symposium on Algorithms, ESA 1995 - Corfu, Greece Duration: 25 Sep 1995 → 27 Sep 1995

Publication series

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

Conference

Conference	3rd Annual European Symposium on Algorithms, ESA 1995
Country/Territory	Greece
City	Corfu
Period	25/09/95 → 27/09/95

Access to Document

10.1007/3-540-60313-1_164

Cite this

Schulz, A. S., Weismantel, R., & Ziegler, G. M. (1995). 0/1-integer programming: Optimization and augmentation are equivalent. In P. Spirakis (Ed.), Algorithms - ESA 1995 - 3rd Annual European Symposium, Proceedings (pp. 473-483). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 979). Springer Verlag. https://doi.org/10.1007/3-540-60313-1_164

Schulz, Andreas S. ; Weismantel, Robert ; Ziegler, Günter M. / 0/1-integer programming : Optimization and augmentation are equivalent. Algorithms - ESA 1995 - 3rd Annual European Symposium, Proceedings. editor / Paul Spirakis. Springer Verlag, 1995. pp. 473-483 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{72bf0255fa3742fe9d27b018f525b2a5,

title = "0/1-integer programming: Optimization and augmentation are equivalent",

abstract = "For every family of sets F ⊆ {0, 1}n the following problems are strongly polynomial time equivalent: given a feasible point x0 ϵ F and a linear objective function c ϵ ℤn, find a feasible point x* ϵ F that maximizes cx (Optimization), _9 find a feasible point xnew ϵ F with cxnew > cx0 (Augmentation), and find a feasible point xnew ϵ F with c xnew > c x0 such that xnew—x0is “irreducible” (Irreducible Augmentation). This generalizes results and techniques that are well known for 0/1- integer programming problems that arise from various classes of combinatorial optimization problems.",

author = "Schulz, {Andreas S.} and Robert Weismantel and Ziegler, {G{\"u}nter M.}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1995.; 3rd Annual European Symposium on Algorithms, ESA 1995 ; Conference date: 25-09-1995 Through 27-09-1995",

year = "1995",

doi = "10.1007/3-540-60313-1_164",

language = "English",

isbn = "3540603131",

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

publisher = "Springer Verlag",

pages = "473--483",

editor = "Paul Spirakis",

booktitle = "Algorithms - ESA 1995 - 3rd Annual European Symposium, Proceedings",

}

Schulz, AS, Weismantel, R & Ziegler, GM 1995, 0/1-integer programming: Optimization and augmentation are equivalent. in P Spirakis (ed.), Algorithms - ESA 1995 - 3rd Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 979, Springer Verlag, pp. 473-483, 3rd Annual European Symposium on Algorithms, ESA 1995, Corfu, Greece, 25/09/95. https://doi.org/10.1007/3-540-60313-1_164

0/1-integer programming: Optimization and augmentation are equivalent. / Schulz, Andreas S.; Weismantel, Robert; Ziegler, Günter M.
Algorithms - ESA 1995 - 3rd Annual European Symposium, Proceedings. ed. / Paul Spirakis. Springer Verlag, 1995. p. 473-483 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 979).

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

TY - GEN

T1 - 0/1-integer programming

T2 - 3rd Annual European Symposium on Algorithms, ESA 1995

AU - Schulz, Andreas S.

AU - Weismantel, Robert

AU - Ziegler, Günter M.

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1995.

PY - 1995

Y1 - 1995

N2 - For every family of sets F ⊆ {0, 1}n the following problems are strongly polynomial time equivalent: given a feasible point x0 ϵ F and a linear objective function c ϵ ℤn, find a feasible point x* ϵ F that maximizes cx (Optimization), _9 find a feasible point xnew ϵ F with cxnew > cx0 (Augmentation), and find a feasible point xnew ϵ F with c xnew > c x0 such that xnew—x0is “irreducible” (Irreducible Augmentation). This generalizes results and techniques that are well known for 0/1- integer programming problems that arise from various classes of combinatorial optimization problems.

AB - For every family of sets F ⊆ {0, 1}n the following problems are strongly polynomial time equivalent: given a feasible point x0 ϵ F and a linear objective function c ϵ ℤn, find a feasible point x* ϵ F that maximizes cx (Optimization), _9 find a feasible point xnew ϵ F with cxnew > cx0 (Augmentation), and find a feasible point xnew ϵ F with c xnew > c x0 such that xnew—x0is “irreducible” (Irreducible Augmentation). This generalizes results and techniques that are well known for 0/1- integer programming problems that arise from various classes of combinatorial optimization problems.

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

U2 - 10.1007/3-540-60313-1_164

DO - 10.1007/3-540-60313-1_164

M3 - Conference contribution

AN - SCOPUS:84947744343

SN - 3540603131

SN - 9783540603139

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

SP - 473

EP - 483

BT - Algorithms - ESA 1995 - 3rd Annual European Symposium, Proceedings

A2 - Spirakis, Paul

PB - Springer Verlag

Y2 - 25 September 1995 through 27 September 1995

ER -

Schulz AS, Weismantel R, Ziegler GM. 0/1-integer programming: Optimization and augmentation are equivalent. In Spirakis P, editor, Algorithms - ESA 1995 - 3rd Annual European Symposium, Proceedings. Springer Verlag. 1995. p. 473-483. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-60313-1_164

0/1-integer programming: Optimization and augmentation are equivalent

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this