Zahlreiche Problemstellungen besitzen in natürlicher Weise Online-Charakter. Sie erfordern Entscheidungen auf der Basis unvollständigen Wissens. In der Online-Optimierung modelliert man daher die Eingabe als eine (endliche) Anfragefolge, die ein Online-Algorithmus stückweise erhält. Nach dem Bekanntwerden einer Anfrage muss der Online-Algorithmus eine Entscheidung über seine weitere Arbeitsweise treffen, ohne die nächsten Anfragen zu kennen. Die Entscheidungen des Online-Algorithmus sind je nach Problem eventuell zusätzlichen Einschränkungen unterworfen.

Wir möchten in diesem Projekt Grundlagenforschung für die Konstruktion und die Analyse von Online-Algorithmen betreiben. Ziel ist es, den übermäßigen Pessimismus der klassischen kompetitiven Analyse (dem "Standard-Mittel" zur theoretischen Beurteilung von Online-Algorithmen) teilweise zu beheben und aussagekräftigere Beurteilungen für Algorithmen herzuleiten.

• DFG-Research Group Algorithms, Structure, Randomness
• Sven O. Krumke, Technische Universität Kaiserslautern
• Jörg Rambau, Universität Bayreuth
• Tjark Vredeveld, Maastricht University