Technical Report 441-1995

Title

0/1-Integer Programming: Optimization and Augmentation are Equivalent

Authors

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

Publication

Springer, Lecture Notes in Computer Science 979, Algorithms - ESA '95, ed. Paul Spirakis, 1995, pp. 473-483

Source

Download as [ps.gz]

Classification

not available

Keywords

not available

Abstract

For every family of sets Fsubseteq{0,1}ⁿ the following problems are strongly polynomial time equivalent: given a feasible point xold&;cal F and a linear objective function c&;Zⁿ, itemize} item find a feasible point x^*&;cal F that maximizes cx (Optimization), item find a feasible point xnew&;cal F with cxnew>cxold (Augmentation), and item find a feasible point xnew&;cal F with cxnew>cxold such that xnew-xold is "irreducible" (Irreducible Augmentation). itemize} This generalizes results and techniques that are well known for 0/1-integer programming problems that arise from various classes of combinatorial optimization problems.