Online Algorithms for Multi-Level Aggregation
Online Algorithms for Multi-Level Aggregation
复制标题
多级聚合的在线算法
DOI：
10.4230/lipics.esa.2016.12
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
P. Veselý
中科院分区：
文献类型：
--
作者：
Marcin Bienkowski;Martin Böhm;J. Byrka;M. Chrobak;C. Dürr;Lukáš Folwarczný;Lukasz Jez;J. Sgall;K. Nguyen;P. Veselý
在多层聚合问题（MLAP）中，请求到达边加权树T的节点，最终必须得到服务。服务被定义为包含其根的T的子树X。该子树X为所有在X节点上挂起的请求提供服务，该服务的成本等于X的总权重。每个请求在到达时间和服务时间之间也会产生等待成本。目标是最小化所有请求的总等待成本加上所有服务子树的总成本。MLAP是一些研究得很好的优化问题的推广；例如，对于深度为1的树，MLAP相当于TCP确认问题，而对于深度为2的树，它相当于联合补给问题。任意深度树的聚合问题出现在组播、传感器网络、组织层级中的通信和供应链管理中。与这些应用程序相关联的MLAP实例自然是在线的，这意味着需要在没有关于未来请求的信息的情况下做出聚合决策。
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 also show several additional lower and upper bound results for some special cases of MLAP, including the Single-Phase variant and the case when the tree is a path.
影响因子：
2
作者：
Bienkowski M
通讯作者：
Bienkowski M