Zufall bei Entwurf und Analyse von diskreten Algorithmen

点击翻译按钮获取中文摘要

Seit den grundlegenden Arbeiten von Cook und Karp sind viele kombinatorische Optimierungsprobleme als NP-schwer nachgewiesen worden. Dies und die später folgende Nichtapproximierbarkeitstheorie sind Indizien dafür, daß die entsprechenden Probleme nicht effizient lösbar sind, ja sogar nicht einmal effizient approximierbar sind - mal in engen, mal in weiten Grenzen. Viele kombinatorische Optimierungsprobleme stellen Abstraktionen praktischer Fragestellungen mit zum Teil enormer wirtschaftlicher Bedeutung dar. In diesem Projekt soll untersucht werden, wie der Zufall bei ihrer Lösung helfen kann. Dazu gibt es vielfältige Ansätze, deren Methoden sich abhängig vom Optimierungsproblem und auch vom Gebrauch des Zufalls stark unterscheiden. In Bezug auf das betrachtete Optimierungsproblem fokussiert das Projekt auf Graphenprobleme, vorwiegend auf Färbung, Planarität und Transport. Der Zufall soll einerseits im Sinne der Leitfrage, Analyse von Algorithmen bei zufälliger Eingabe, und andererseits im Sinne der Leitfrage, Analyse von Algorithmen, die Zufall nutzen, eingesetzt werden. Nach einer kurzen programmatischen Einleitung werden vier Felder vorgestellt, auf die sich die Arbeit konzentrieren soll. Der Stand der Forschung und eigene Vorarbeiten werden dabei jeweils zusammengefasst.