Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

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

Zitieren Sie bitte immer diese 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.}

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Andreas S. Schulz, Robert Weismantel, Günter M. Ziegler
Dokumentart:ZIB-Report
Datum der Erstveröffentlichung:22.03.1995
Schriftenreihe (Bandnummer):ZIB-Report (SC-95-08)
ZIB-Reportnummer:SC-95-08
Verlagspublikation: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
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.