Algorithm Engineering zur Methodenentwicklung im randomisierten Runden

• Antragsteller: Professor Dr. Benjamin Doerr
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2007 bis 2015
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 47940037

Randomisiertes Runden ist eines der ‘‘Design-Paradigmen’’ zum Entwurf randomisierter Algorithmen �vgl. Hromokovic [Hro05]). Leider offenbart sich eine große Lücke zwischen Theorie und Praxis. Während randomisiertes Runden der Kern vieler Algorithmen mit sehr guten theoretischen Eigenschaften ist, gibt es nur vereinzelte Arbeiten, die es in speziellen Situationen nutzen. Dies wird der Universalität des Verfahrens nicht gerecht. Der Vorsprung der Theorie wurde durch die Arbeiten des Antragstellers in den letzten Jahren noch vergrößert. Die von Antragsteller entwickelten Algorithmen sind aber nicht nur mächtiger als die bisherigen, sie versprechen auch eine einfachere praktische Nutzung. Dies erhöht die Chance, die Diskrepanz zwischen theoretischer und praktischer Methodenentwicklung im randomisierten Runden zu überwinden. Ziel des Antrages ist daher, die neuen Algorithmen unter der Herangehensweise des ‘‘Algorithm Engineering’’ bis hin zur Praxisreife weiterzuentwickeln.

• DFG-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1307: Algorithm Engineering