Chair of Theoretical Computer Science and Information Security






  • FacebookTwitterYoutube
  • Deutsch

Approximation von Independent Set in zufälligen uniformen Hypergraphen in polynomieller erwarteter Zeit

Talking persons:
Dipl.-Inf. Kai Plociennik
Abstract:
Dieser Vortrag ist Teil des Workshops "Algorithmen und Graphen".

Für das Problem Independent Set in uniformen Hypergraphen ist bekannt, dass es für kein ε > 0 einen polynomiellen Approximationsalgorithmus mit Güte n^{1- ε} gibt.

Im Vortrag wird ein deterministischer Algorithmus gezeigt, der für ein bestimmtes Modell zufälliger uniformer Hypergraphen eine polynomielle erwartete Laufzeit besitzt, und eine Güte hat, die die Grenze n^{1- ε} unterbietet.
Times:
Monday 14th January 2008, 6.15 pm - 6.45 pm, room 1/346