Birgit Engels
Zentrum für Angewandte Informatik Köln
Universität zu Köln

Instant recognition of halfintegrality and 2-approximations part II

Im Artikel "Instant recognition of halfintegrality and 2-approximations" von D. Hochbaum werden IPs mit spezieller Struktur (2VAR-Struktur und zusätzliche Bedingungen) betrachtet. Diese können in (pseuso)polynomieller Zeit ganzzahlig, halbzahlig oder im allgemeinsten Fall mit gewissen anderen konstruktionsbedingten fraktionalen superoptimalen Lösungen gelöst werden. Letztere werden als Ausgangspunkte zu ganzzahligen Approximationslösungen verwendet.

Wir haben gesehen, wie IPs mit 2VAR-Struktur unter begrenztem Verlust der Ganzzahligkeit monotonisiert und binarisiert werden koennen. Nun wollen wir für das entstandene IP mit manipulierten Bedingungen eine Lösung über den maximalen Fluss in einem zu kontruierenden Graphen finden.