@misc{SchulzWeismantelZiegler1995, author = {Schulz, Andreas S. and Weismantel, Robert and Ziegler, G{\"u}nter M.}, title = {0/1-Integer Programming: Optimization and Augmentation are Equivalent}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1744}, number = {SC-95-08}, year = {1995}, abstract = {{\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.}}, language = {en} }