Probabilistische Approximation von Shortest Common Superstring
| Talking persons: |
| Dipl.-Inf. Kai Plociennik |
| Abstract: |
| Das Problem, für eine Menge von Strings einen Superstring zu bestimmen, in dem alle gegebenen Strings als Substring (geschlossener Block) vorkommen, und der möglichst kurz ist, ist NP-hart, und es gibt unter vernünftigen Komplexitätstheoretischen Voraussetzungen auch kein Polynomielles Approximationsschema. Es wird gezeigt, wie man eine Art Approximationsschema erhält, wenn man sich damit zufrieden gibt, dass der Algorithmus auf zufälligen Eingaben erwartete polynomielle Laufzeit hat. |
| Times: |
| Tuesday 21st November 2006, 3.30 pm - 5.00 pm, room 1/B006 |
