New results on multi-level aggregation

0540790 - MÚ 2022 RIV NL eng J - Journal Article
Bienkowski, M. - Böhm, M. - Byrka, J. - Chrobak, M. - Dürr, Ch. - Folwarczný, Lukáš - Jeż, Ł. - Sgall, J. - Thang, N. K. - Veselý, P.
New results on multi-level aggregation.
Theoretical Computer Science. Roč. 861, March 12 (2021), s. 133-143. ISSN 0304-3975. E-ISSN 1879-2294
R&D Projects: GA ČR(CZ) GX19-27871X
Institutional support: RVO:67985840
Keywords : algorithmic aspects of networks * online algorithms * scheduling and resource allocation
OECD category: Pure mathematics
Impact factor: 1.002, year: 2021
Method of publishing: Limited access
https://doi.org/10.1016/j.tcs.2021.02.016

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.
Permanent Link: http://hdl.handle.net/11104/0318386