Average-Case Analyse parametrisierter & probabilistischer Algorithmen

Ein Problem, stellt sich als NP-vollständig heraus. Sehr wahrscheinlich gibt es also keinen schnellen Algorithmus, der das Problem löst. Was also tun? Sich mit dieser eher unbefriedigenden Antwort der klassischen (Worst-Case)- Komplexitätstheorie abzugeben und die Aufgabe ungelöst zurückzulassen, ist insbesondere in der Praxis oft kein denkbarer Umgang mit der Situation. Doch es gibt einige Ansätze, wie man sich dennoch diesen schwierigen Problemen nähern kann: Multivariate Komplexitätstheorie betrachtet die Abhängigkeit von weiteren Parametern, bei einer Average-Case-Analyse wird die durchschnittliche Laufzeit betrachtet. Probabilistische Algorithmen können zu besseren Ergebnissen gelangen. Und Approximations-Algorithmen gute Näherungen liefern. Diese Ansätze sind jeder für sich gut untersucht, Querverbindungen zwischen ihnen jedoch nur spärlich. Dies will die vorliegende Arbeit ändern und aufzeigen, wo sich die verschiedenen Herangehensweisen gegenseitig unterstützen, um bessere Ergebnisse und schnellere Algorithmen entwickeln zu können.

Dr. Christian Hercher, Dipl.-Math.: Studium der Mathematik und Informatik an der FSU Jena und RWTH Aachen. Software-Entwickler. Wissenschaftlicher Mitarbeiter an der Europa-Universität Flensburg.