Kombinatorische Online-Planung

• Antragsteller: Professor Dr. Martin Grötschel
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2001 bis 2007
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5467699

Wir möchten in diesem Projekt für Online-Planungsprobleme im Zeitstempelmodell (z.B. für Online-Transportprobleme) Modifikationen der kompetitiven Analyse und gänzlich neue Konzepte entwickeln, die es erlauben, die Güte von Online-Algorithmen einerseits zu verbessern und andererseits praxisrelevanter beurteilen zu können, als es mit klassischer kompetitiver Analyse derzeit möglich ist. Hierbei stehen drei Ansätze im Mittelpunkt: - Randomisierte Online-Algorithmen entschärfen singuläre Worst-Case-Szenarien. - Die Betrachtung zufälliger Eingabesequenzen gemäß einer Wahrscheinlichkeitsverteilung liefert Ergebnisse, die für "typische" Eingaben aussagekräftig sind (Average-Case-Analyse). - Die Untersuchung der Struktur praktisch sinnvoller Anfragesequenzen durch mathematische Beschreibung von Restriktionen kann "absurde" Anforderungen des Offline-Gegenspielers eliminieren.

• DFG-Verfahren: Forschungsgruppen
• Teilprojekt zu: FOR 413: Algorithmen, Struktur, Zufall