Algorithm Engineering zur Methodenentwicklung im randomisierten Runden

• Applicant: Professor Dr. Benjamin Doerr
• Subject Area: Theoretical Computer Science
• Term: from 2007 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Priority Programmes
• Subproject of: SPP 1307: Algorithm Engineering