Probabilistische Analyse diskreter Optimierungsprobleme

• Antragsteller: Professor Dr. Berthold Vöcking (†)
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2005 bis 2008
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 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-Verfahren: Sachbeihilfen