Online problems and two-player games : algorithms and analysis

In this thesis we study three problems that are adversarial in nature. Such problems can be viewed as a game between an algorithm and an adversary, where the adversary always tries to force the algorithm into worst-case scenarios during its execution. Many real world problems with inherent uncertainty or lack of information fit into this model. For instance, it includes the vast field of online problems where the input is only partially available and an adversary reveals the complete input gradually over time (online fashion). The algorithm has to perform efficiently under this uncertainty. In contrast to the online setting, in an offline setting, the complete input is available in the beginning. The first problem that we investigate is a classical online scheduling problem where a sequence of jobs that arrive online have to be assigned to a set of identical machines with the objective of minimizing the maximum load. We study a natural generalization of this problem where we allow migration of already scheduled jobs to other machines upon the arrival of a new job, thus bridging the gap between online and offline setting. Already for a small amount of migration, our result compares with the best results to date in both online and offline settings. From the point of view of sensitivity analysis, our results imply that, only small changes are to be made to the current schedule to accommodate a new job, if we are satisfied with near optimal solution. The other online problem that we study is the well-known metrical task systems problem. We present a probabilistic analysis of the well-known text book algorithm called the work function algorithm. Besides average-case analysis we also present smoothed analysis, which is a notion introduced recently as a hybrid between worst-case and average-case analysis. Our analysis reveals that the performance of this algorithm is much better than worst-case for a large class of inputs. This motivates us to support smoothed analysis as an alternative model for evaluating the performance of online algorithms. The third problem that we investigate is a pursuit-evasion game: an algorithm (the pursuer) has to find/catch an adversary that is 'hiding'; in a graph where both players can travel in the graph. This problem belongs to the rich field of search games and it addresses the question of how long it takes for the pursuer to find the evader in a given graph that, for example, corresponds to a computer network or a geographic terrain. Such game models are also used to design efficient communication protocols. We present improved results against adversaries with varying power and also present tight lower bounds.In der vorliegenden Arbeit beschäftigen wir uns mit drei Problemen, welche als eine Art Spiel zwischen einem Algorithmus und seinem Gegenspieler interpretiert werden können. In diesem Spiel versucht der Gegenspieler, den Algorithmus während seiner Ausführung in sein Worst-Case Verhalten zu zwingen. Eine Vielzahl von praxisrelevanten Problemen, in denen nicht von Beginn an die volle Information über die Eingabeinstanz zur Verfügung steht, lassen sich als derartige Spiele modellieren. Zu dieser Klasse von Problemen gehören z. B. auch online Probleme, in denen der Gegenspieler die Eingabeinstanz für den Algorithmus online, d. h. während der Ausführung des Algorithmus, spezifiziert. Das Ziel des Algorithmus ist es, auf dieser so spezifizierten Instanz möglichst effizient zu sein. Im Gegensatz zum online Szenario kennt der Algorithmus im offline Szenario die gesamte Eingabeinstanz gleich von Beginn an. Im online Szenario wird die Effizienz eines (online) Algorithmus anhand seines Competitive Ratio gemessen. Ein Algorithmus ist c-competitive, wenn die Kosten, die der Algorithmus auf einer beliebigen online Eingabe verursacht, maximal einen Faktor c von den Kosten eines optimalen (offline) Algorithmus, der die gesamte Eingabe kennt, entfernt ist. Das erste Problem, dass wir betrachten, ist ein klassisches Scheduling Problem, in dem Jobs online eintreffen und auf identischen parallelen Maschinen verteilt werden müssen. Das Ziel ist es, die maximale Maschinenlast zu minimieren. Das zweite online Problem, dass wir betrachten, ist das Metrical Task System Problem. Als drittes Problem analysieren wir ein "Katz-und-Maus-Spiel';: eine Katze (der Algorithmus) und eine Maus (der Gegenspieler) befinden sich in einem Graphen und die Katze versucht, die Maus zu fangen