Ein Approximationsalgorithmus für das Problem Minimum Maximal Independence Number in zufälligen Hypergraphen
| Vortragende(r): |
| Dipl.-Inf. Kai Plociennik |
| Inhalt: |
| Das Problem, eine minimale inklusionsmaximale unabhängige Menge in Graphen zu bestimmen, ist nicht nur NP-hart, sondern lässt sich auch schwer in Polynomialzeit approximieren. Im Vortrag wird ein Algorithmus vorgestellt, der eine bessere Approximationsgüte garantiert, als es im worst case effiziente Algorithmen garantieren können, und der immerhin noch polynomielle erwartete Rechenzeit besitzt bzgl. zufälliger Eingaben eines "vernünftigen" Modells von zufälligen Hypergraphen. |
| Zeiten: |
| Dienstag, der 22.05.2007, 15:45 - 16:45 Uhr, Raum 1/208A |
