Advice and Randomization in Online Computation
Dennis Komm · Repository for Publications and Research Data (ETH Zurich) · 2012
Online computation is both of theoretical interest and practical relevance as numerous computational problems require a model in which algorithms do not know the whole input at every time step during runtime.The established measurement for the output quality of these online algorithms is the so-called competitive analysis, introduced by Sleator and Tarjan in 1985.Similar to the decrease in accuracy we have to accept when efficiently (i.e., in polynomial time) solving N P-hard problems, the competitive ratio describes what we have to pay for not knowing the future.In this thesis, we want to measure how much additional information is both necessary and sufficient to escape from this dilemma, i. e., we want to understand what causes this, for the majority of problems, vast amount of precision we lose due to facing an online scenario.More specifically, we want to study the advice complexity of online problems, which describes the amount of information online algorithms lack, causing them to fail (compared to hypothetical offline algorithms that know all yet unrevealed parts of the input from the start).In the model used throughout this thesis, we equip online algorithms with an additional advice tape onto which an oracle, which sees the whole input before the algorithm is executed, may write binary information.The algorithm can then use these advice bits during computation.We call the minimum number of advice bits needed to compute an optimal solution for some online problem the information content of this problem.This information is what needs to be extracted from the instance in order to overcome the drawback of not completely knowing it in advance.We know that there exist well-studied online problems for which any solution computed by a deterministic online algorithm is (asymptotically) half as good as the optimal solution, because it does not know future input parts.However, a single bit of advice suffices to perform optimally.For many other problems, measuring the information content proves to be a more complicated task.Moreover, generalizing this idea, we study the tradeoff between obtaining highquality results (i.e., creating online algorithms with a reasonable competitive ratio) and the number of advice bits both necessary and sufficient for this.We study five online problems within the framework described above, the job shop scheduling problem with two jobs and unit-length tasks, the disjoint path allocation problem, the k-server problem, the set cover problem, and the knapsack problem.It turns out that online problems may behave very differently in terms of advice complexity.There are, for instance, problems that achieve very good results with a constant number of advice bits and other ones that, if given less advice than linear in the input size, are doomed to fail.Specifically, we ask how many advice bits are necessary and sufficient to (i) be optimal, (ii) to improve over purely deterministic strategies, or (iii) to be on par with (or better than) randomized strategies.Since we may look at computing with advice as supplying the best possible random string for any input, we are particularly interested in the last point and the further relai