PhD thesis defense to be held on May 27, 2021, at 11:00 (Teleconference via Webex)

Picture Credit: Loukas Kavouras

Thesis title: Online Algorithms for Dynamic Aggregation problems

Abstract: We study online variants of Dynamic Aggregation problems that are generalizations of prominent and well studied online problems. In the online setting, we 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 worst-case ratio between the online cost and the optimal offline cost is called the competitive ratio.

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 of the upper bounds that we show are close (or the same) with the lower bounds that we prove and this ensures that our online algorithms are optimal or near optimal.

Supervisor: Dimitris Fotakis, Associate Professor

PhD Student: Loukas Kavouras