Approximation von Independent Set in zufälligen uniformen Hypergraphen in polynomieller erwarteter Zeit
| Vortragende(r): |
| Dipl.-Inf. Kai Plociennik |
| Inhalt: |
| 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. |
| Zeiten: |
| Montag, der 14.01.2008, 18:15 - 18:45 Uhr, Raum 1/346 |
