Refine
Year of publication
- 1995 (1)
Document Type
- ZIB-Report (1)
Language
- English (1)
Has Fulltext
- yes (1)
Is part of the Bibliography
- no (1)
Institute
- ZIB Allgemein (1)
{\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.}