Please use this identifier to cite or link to this item:
Title: Online Algorithms for Dynamic Aggregation Problems
Authors: Kavouras, Loukas
Φωτάκης Δημήτριος
Keywords: Algorithms
Online Algorithms
Dynamic Aggregation
Issue Date: 27-May-2021
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.
Appears in Collections:Διδακτορικές Διατριβές - Ph.D. Theses

Files in This Item:
File Description SizeFormat 
Kavouras_thesis.pdf1.12 MBAdobe PDFView/Open

Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.