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

Instant recognition of halfintegrality and 2-approximations

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.