Zufall bei Entwurf und Analyse von diskreten Algorithmen

• Applicant: Professor Dr. Mathias Schacht, since 10/2007
• Subject Area: Mathematics
• Term: from 2001 to 2009
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5467699

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.

• DFG Programme: Research Units
• Subproject of: FOR 413: Algorithms, Structure, Randomness
• Ehemaliger Antragsteller: Professor Dr. Hans Jürgen Prömel, until 10/2007