Online Algorithms for Dynamic Aggregation Problems

Abstract

In this Ph.D thesis, we study online variants of Dynamic Aggregation problems that are generalizations of prominent and well studied online problems. In the online setting, we additionally assume that the input arrives piece-by-piece and that the online algorithm has to provide a solution for the input piece of the current stage before it sees the upcoming input pieces of future stages. The decision quality of the online algorithm is evaluated against an optimal offline algorithm, which is given the whole problem data from the beginning. The performance of the online algorithm is measured by the competitive ratio which is the worst-case ratio between the online cost and the optimal offline cost. We consider the online variants of the Min-Sum Set Cover problem, the K-Facility Reallocation problem and the Dynamic Facility Location problem. For all the aforementioned problems, we design online algorithms and we prove upper bounds on their competitive ratio. Moreover, we construct difficult instances for these problems and we prove lower bounds on the competitive ratio of online algorithms on these instances. The majority the upper bounds are close (or the same) with the lower bounds that we prove and this ensures that our online algorithms are optimal or near optimal.