Ein probabilistisches Approximationsschema für Shortest Common Superstring
| Talking persons: |
| Dipl.-Inf. Kai Plociennik |
| Abstract: |
| Das Problem Shortest Common Superstring hat Anwendungen z.B. in der Bioinformatik und der Datenkompression. Es ist bekannt, dass es sich unter der Annahme P ungleich NP nicht bis auf eine beliebig kleine konstante Güte approximieren lässt, wenn man effiziente Algorithmen betrachtet. Im Vortrag wird ein Algorithmus vorgestellt, der eine beliebig gute Approximation liefern kann, und der auf zufälligen Eingaben im Erwartungswert effizient ist. |
| Times: |
| Tuesday 20th October 2009, 11.30 am - 12.30 pm, room 1/208 |
