New results on multi-level aggregation

Autor: Marek Chrobak, Łukasz Jeż, Nguyen Kim Thang, Martin Böhm, Pavel Veselý, Jiří Sgall, Christoph Dürr, Jaroslaw Byrka, Marcin Bienkowski, Lukáš Folwarczný
Přispěvatelé: Institute of Computer Science, University of Wrocław [Poland] (UWr), Computer Science Institute, Charles University [Prague] (CU), FB3: Mathematik/Informatik, University of Bremen, Department of Computer Science, University of California [Riverside] (UCR), University of California-University of California, Recherche Opérationnelle (RO), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Institute of Mathematics, Heyrovský Institute of Physical Chemistry of the Czech Academy of Sciences (HIPC / CAS), Czech Academy of Sciences [Prague] (CAS)-Czech Academy of Sciences [Prague] (CAS), Informatique, BioInformatique, Systèmes Complexes (IBISC), Université d'Évry-Val-d'Essonne (UEVE)-Université Paris-Saclay, University of Warwick [Coventry], University of California [Riverside] (UC Riverside), University of California (UC)-University of California (UC), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)
Jazyk: angličtina
Rok vydání: 2021
Předmět:
Zdroj: Theoretical Computer Science
Theoretical Computer Science, Elsevier, 2021, 861, pp.133-143. ⟨10.1016/j.tcs.2021.02.016⟩
Theoretical Computer Science, 2021, 861, pp.133-143. ⟨10.1016/j.tcs.2021.02.016⟩
Theoretical Computer Science, Elsevier, 2021, 861, pp.133--143. ⟨10.1016/j.tcs.2021.02.016⟩
ISSN: 1879-2294
0304-3975
Popis: In the Multi-Level Aggregation Problem ( MLAP ), requests for service arrive at the nodes of an edge-weighted rooted tree T . Each service is represented by a subtree X of T that contains its root. This subtree X serves all requests that are pending in the nodes of X, and the cost of this service is equal to the total weight of X. Each request also incurs a waiting cost between its arrival and service time. The objective is to minimize the total waiting cost of all requests plus the total cost of all service subtrees. The currently best online algorithms for the MLAP achieve competitive ratios polynomial in the tree depth, while the best lower bound is only 3.618. In this paper, we report some progress towards closing this gap, by improving this lower bound and providing several tight bounds for restricted variants of MLAP : (1) We first study a Single-Phase variant of MLAP where all requests are released at the beginning and expire at some unknown time θ, for which we provide an online algorithm with optimal competitive ratio of 4. (2) We prove a lower bound of 4 on the competitive ratio for MLAP , even when the tree is a path. We complement this with a matching upper bound for the deadline variant of MLAP on paths. Additionally, we provide two results for the offline case: (3) We prove that the Single-Phase variant can be solved optimally in polynomial time, and (4) we give a simple 2-approximation algorithm for offline MLAP with deadlines.
Databáze: OpenAIRE
Externí odkaz: