Approximative, randomisierte und probalistische Algorithmen für kombinatorische Optimierungsprobleme

• Applicant: Professor Dr. Hans Jürgen Prömel
• Subject Area: Theoretical Computer Science
• Term: from 1999 to 2004
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5174648

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.

• DFG Programme: Research Grants