Probabilistische Analyse diskreter Optimierungsprobleme

• Applicant: Professor Dr. Berthold Vöcking (†)
• Subject Area: Theoretical Computer Science
• Term: from 2005 to 2008
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5453742

Viele algorithmische Probleme sind hart für Worst-Case-Eingaben, aber dennoch gibt es Heuristiken für diese Probleme, die auf typischen Eingaben sehr effizient arbeiten. Das in diesem Antrag vorgeschlagene Forschungsprojekt beschäftigt sich mit der probabilistischen Analyse von derartigen Problemen. Im Zentrum unserer Untersuchungen stehen Optimierungsprobleme, die sich in Form von ganzzahligen linearen Programmen beschreiben lassen. Diese Probleme sollen in verschiedenen probabilistischen Eingabemodellen untersucht werden, die von der klassischen Average-CaseAnalyse bis hin zu fortgeschrittenen Analysekonzepten wie der geglätteten Analyse (Smoothed Analysis) reichen. Zielsetzung dieses Projektes ist es, ein verbessertes theoretisches Verständnis der strukturellen Eigenschaften von typischen Probleminstanzen zu erlangen, um den Erfolg von Heuristiken wie Core- oder Branch-and-Bound-Methoden theoretisch erklären und sie dadurch verbessern zu können, oder auch die Entwicklung völlig neuartiger Verfahren zu ermöglichen. Unser Forschungsansatz ist zweistufig. Er basiert einerseits auf der probabilistischen Analyse struktureller Kenngrößen, wie z.B. der Anzahl pareto-optimaler Lösungen oder auch der Größe des Integrality Gaps, und andererseits auf der Bestimmung von Laufzeitschranken in Abhängigkeit von diesen Kenngrößen. Die im Zentrum dieses Projektes stehenden theoretischen Analysen sollen durch experimentelle Untersuchungen unterstützt werden.

• DFG Programme: Research Grants