<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>174</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1995-03-22</completedDate>
    <publishedDate>1995-03-22</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">0/1-Integer Programming: Optimization and Augmentation are Equivalent</title>
    <abstract language="eng">{\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&gt;cx$ (Augmentation), and \item find a feasible point $\xnew\in\cal F$ with $c\xnew&gt;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.}</abstract>
    <identifier type="serial">SC-95-08</identifier>
    <identifier type="opus3-id">174</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-1744</identifier>
    <enrichment key="SourceTitle">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</enrichment>
    <author>Andreas S. Schulz</author>
    <author>Robert Weismantel</author>
    <author>Günter M. Ziegler</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-95-08</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/174/SC-95-08.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/174/SC-95-08.pdf</file>
  </doc>
</export-example>
