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 |
