Universität zu Köln
Mathematisch-Naturwissenschaftliche Fakultät
ZAIK Arbeitsgruppe Faigle/Schrader
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.
© ZAIK Arbeitsgruppe Faigle/Schrader, letzte Änderung: 09.02.2009