Approximation von INDEPENDENT SET in erwarteter Polynomialzeit
| Talking persons: |
| Dipl.-Inf. Kai Plociennik |
| Abstract: |
| Das Problem INDEPENDENT SET (Finde eine möglichst große unabhängige Menge in einem gegebenen Graphen, d.h. eine Teilmenge der Knoten die keine Kanten enthält) ist eines der klassischen NP-harten Probleme. Ein neueres Resultat zeigt, dass es auch schwierig zu approximieren ist, d.h. unter der Voraussetzung P ungleich NP ist keine vernünftige Approximationsgüte in Polynomialzeit garantierbar. Im Vortrag wird vorgestellt, wie sich dieses Problem auf Hypergraphen besser approximieren lässt, wenn man zufällige Eingaben (Hypergraphen) betrachtet und nur verlangt, dass der Algorithmus auf diesen Eingaben im Erwartungswert polynomielle Laufzeit hat. |
| Times: |
| Tuesday 25th October 2005, 3.30 pm - 5.00 pm, room 1/208A |
