Approximative, randomisierte und probalistische Algorithmen für kombinatorische Optimierungsprobleme

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

In unserem Forschungsvorhaben sollen zum einen möglichst gute Approximationsalgorithmen gefunden werden oder aber bestimmt werden, welche Schranke die Approximationsgüte in polynomineller Zeit nicht übrschreiten kann. Die Untersuchungen werden sich vor allem auf einen Problemkreis konzentrieren, in dessen Mittelpunkt das Steinerbaumproblem und einige bezüglich ihres Approximationsverhaltens eng damit verflochtene Probleme stehen. Dem Forschungsvorhaben liegt hier die Vision zugrunde, daß man durch Einsichten in den Phasenübergang zwischen Approximnierbarkeit und Nichtapproximierbarkeit letztendlich auch ein besseres Verständnis des Phasenübergangs zwischen P und NP erlangt. Andererseits sollen im Sinne einer probabilistischen Analyse solche Algorithmen untersucht werden, die eine erwartet gute oder sogar optimale Lösung in erwartet polynomieller Laufzeit finden. Unsere besonderes Interesse gilt dabei dem bei der Praxis auftretenden Problemen vielfach sehr eingeschränkten Instanzenbereich.