Ein probabilistisches PTAS für Shortest Common Superstring
| Talking persons: |
| Dipl.-Inf. Kai Plociennik |
| Abstract: |
| Es wird das durch Anwendungen in der Bioinformatik und der Datenkompression motivierte Shortest Common Superstring Problem betrachtet. Hierbei möchte man zu einer Menge von Strings über einem festen Alphabet einen möglichst kurzen String finden (den "Superstring"), der alle Strings aus der Eingabe als geschlossene Substrings enthält. Unter vernünftigen komplexitätstheoretischen Annahmen lässt sich das Problem in Polynomialzeit nicht beliebig gut approximieren. Wir zeigen, dass dies sehr wohl möglich ist, wenn man zufällige Eingaben betrachtet und nur verlangt, dass die erwartete Laufzeit bzgl. der zufälligen Eingaben polynomiell ist. |
| Times: |
| Wednesday 29th October 2008, 3.30 pm - 5.00 pm, room 1/367A |
