Back to search

National Technical University of Athens (NTUA)

Online algorithms for dynamic aggregation problems

Abstract

dc:description

In this PhD 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.

Degree

thesis:*
Grantor dc:publisher
National Technical University of Athens (NTUA)
Year dc:date
2021

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Kavouras, Loukas
  • Κάβουρας, Λουκάς

Subjects

dc:subject × 8

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/49595

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Kavouras, Loukas; Κάβουρας, Λουκάς. Online algorithms for dynamic aggregation problems. National Technical University of Athens (NTUA), 2021. http://hdl.handle.net/10442/hedi/49595