Ein Approximationsalgorithmus für das Problem Minimum Maximal Independence Number in zufälligen Hypergraphen
| Talking persons: |
| Dipl.-Inf. Kai Plociennik |
| Abstract: |
| 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. |
| Times: |
| Tuesday 22nd May 2007, 3.45 pm - 4.45 pm, room 1/208A |
