Combinatorial Online Planning

• Applicant: Professor Dr. Martin Grötschel
• Subject Area: Mathematics
• Term: from 2001 to 2007
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Research Units
• Subproject of: FOR 413: Algorithms, Structure, Randomness