Algorithm Engineering zur Methodenentwicklung im randomisierten Runden

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

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.