Skip to Main content Skip to Navigation
New interface
Journal articles

New results on multi-level aggregation

Abstract : In the Multi-Level Aggregation Problem (MLAP ), requests for service arrive at the nodes of an edge-weighted rooted tree . Each service is represented by a subtree X of 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.
Document type :
Journal articles
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03377715
Contributor : Christoph Dürr Connect in order to contact the contributor
Submitted on : Thursday, October 14, 2021 - 11:47:26 AM
Last modification on : Wednesday, November 30, 2022 - 3:34:40 AM

Links full text

Identifiers

Citation

Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, et al.. New results on multi-level aggregation. Theoretical Computer Science, 2021, 861, pp.133-143. ⟨10.1016/j.tcs.2021.02.016⟩. ⟨hal-03377715⟩

Share

Metrics

Record views

48