0/1-Integer Programming: Optimization and Augmentation are Equivalent
Please always quote using this URN: urn:nbn:de:0297-zib-1744
- {\def\xnew{x^{\mbox{\tiny new}}}\def\Z{{{\rm Z}\!\! Z}}For every fixed set ${\cal F}\subseteq\{0,1\}^n$ the following problems are strongly polynomial time equivalent: given a feasible point $x\in\cal F$ and a linear objective function $c\in\Z^n$, \begin{itemize} \item find a feasible point $x^*\in\cal F$ that maximizes $cx$ (Optimization), \item find a feasible point $\xnew\in\cal F$ with $c\xnew>cx$ (Augmentation), and \item find a feasible point $\xnew\in\cal F$ with $c\xnew>cx$ such that $\xnew-x$ is ``irreducible''\\(Irreducible Augmentation). \end{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.}
Download full text files
Additional Services
| Author: | Andreas S. Schulz, Robert Weismantel, Günter M. Ziegler |
|---|---|
| Document Type: | ZIB-Report |
| Date of first Publication: | 1995/03/22 |
| Series (Serial Number): | ZIB-Report (SC-95-08) |
| ZIB-Reportnumber: | SC-95-08 |
| Published in: | Appeared in: Algorithms - ESA 95. 3rd annual European symposium, Corfu, Greece, Sept. 25-27, 1995. Proceedings. Paul Spirakis (ed.) Berlin: Springer 1995. (Lecture notes in computer science, 979). Pp. 473-483 |
