New results on multi-level aggregation

• Published in: Theoretical computer science 2021-03, Vol.861, p.133-143
• Main Authors: Bienkowski, Marcin, Böhm, Martin, Byrka, Jaroslaw, Chrobak, Marek, Dürr, Christoph, Folwarczný, Lukáš, Jeż, Łukasz, Sgall, Jiří, Thang, Nguyen Kim, Veselý, Pavel
• Format: Article
• Language: English
• Subjects: Algorithmic aspects of networks; Computer Science; Data Structures and Algorithms; Online algorithms; Scheduling and resource allocation
• ISSN: 0304-3975; 1879-2294
• DOI: 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.