ISBN 9783843905411

978-3-8439-0541-1, Reihe Mathematik

Benjamin Hiller
Online Optimization: Probabilistic Analysis and Algorithm Engineering

187 Seiten, Dissertation Technische Universität Berlin (2010), Softcover, A5

Zusammenfassung / Abstract

The subject of this thesis is online optimization, which deals with making decisions in an environment where the data describing the process to optimize becomes available over time, i.e. online. In particular, we study combinatorial online optimization problems involving discrete decisions both from a practical and a theoretical point of view.

The first part of the thesis is devoted to reoptimization algorithms for the online control of complex real-world systems. A reoptimization algorithm obtains its online control decision by determining a decision that is in some sense "good" for the current state of the system. We apply rigorous mathematical modelling and optimization methods based on Integer Progamming to develop advanced reoptimization algorithms for two real-world applications: the automatic dispatching of a large fleet of service vehicles to serve waiting customers and the scheduling of groups of passenger elevators in high rise buildings. For both applications we find that rigorous methods improve the performance of the dispatching process, leading to shorter waiting times for the customers / passengers.

The second part introduces a novel kind of probabilistic analysis for online algorithms. In contrast to existing probabilistic analyses, we do not judge the quality of an online algorithm using the expectation of the objective. Instead, we consider the distribution of the objective value on all inputs which gives a more global description of the performance of the algorithm. Using the notion of stochastic dominance, we are able to establish that certain online algorithms obtain better objective value distributions than others. For instance, we can show that the famous paging algorithm LRU achieves a distribution that is optimal w.r.t. the stochastic dominance order if the request sequences exhibit locality of reference. We also apply this approach to the analysis of algorithms for online bin coloring, obtaining a result that explains the behavior observed in simulations, thus resolving an open problem.