License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.12
URN: urn:nbn:de:0030-drops-63637
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6363/
Bienkowski, Marcin ;
Böhm, Martin ;
Byrka, Jaroslaw ;
Chrobak, Marek ;
Dürr, Christoph ;
Folwarczny, Lukas ;
Jez, Lukasz ;
Sgall, Jiri ;
Kim Thang, Nguyen ;
Vesely, Pavel
Online Algorithms for Multi-Level Aggregation
Abstract
In the Multi-Level Aggregation Problem (MLAP), requests arrive at the nodes of an edge-weighted tree T, and have to be served eventually. A service is defined as 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 waiting cost between its arrival and service times. The objective is to minimize the total waiting cost of all requests plus the total cost of all service subtrees. MLAP is a generalization of some well-studied optimization problems; for example, for trees of depth 1, MLAP is equivalent to the TCP Acknowledgment Problem, while for trees of depth 2, it is equivalent to the Joint Replenishment Problem. Aggregation problem for trees of arbitrary depth arise in multicasting, sensor networks, communication in organization hierarchies, and in supply-chain management. The instances of MLAP associated with these applications are naturally online, in the sense that aggregation decisions need to be made without information about future requests.
Constant-competitive online algorithms are known for MLAP with one or two levels. However, it has been open whether there exist constant competitive online algorithms for trees of depth more than 2. Addressing this open problem, we give the first constant competitive online algorithm for networks of arbitrary (fixed) number of levels. The competitive ratio is O(D^4*2^D), where D is the depth of T. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines. We include several additional results in the paper. We show that a standard lower-bound technique for MLAP, based on so-called Single-Phase instances, cannot give super-constant lower bounds (as a function of the tree depth). This result is established by giving an online algorithm with optimal competitive ratio 4 for such instances on arbitrary trees. We also study the MLAP variant when the tree is a path, for which we give a lower bound of 4 on the competitive ratio, improving the lower bound known for general MLAP. We complement this with a matching upper bound for the deadline setting.
BibTeX - Entry
@InProceedings{bienkowski_et_al:LIPIcs:2016:6363,
author = {Marcin Bienkowski and Martin B{\"o}hm and Jaroslaw Byrka and Marek Chrobak and Christoph D{\"u}rr and Lukas Folwarczny and Lukasz Jez and Jiri Sgall and Nguyen Kim Thang and Pavel Vesely},
title = {{Online Algorithms for Multi-Level Aggregation}},
booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)},
pages = {12:1--12:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-015-6},
ISSN = {1868-8969},
year = {2016},
volume = {57},
editor = {Piotr Sankowski and Christos Zaroliagis},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6363},
URN = {urn:nbn:de:0030-drops-63637},
doi = {10.4230/LIPIcs.ESA.2016.12},
annote = {Keywords: algorithmic aspects of networks, online algorithms, scheduling and resource allocation}
}
|
Keywords: |
|
algorithmic aspects of networks, online algorithms, scheduling and resource allocation |
|
Collection: |
|
24th Annual European Symposium on Algorithms (ESA 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
18.08.2016 |
