O(depth)-Competitive Algorithm for Online Multi-level Aggregation
O(depth)-Competitive Algorithm for Online Multi-level Aggregation
复制标题
O(深度)-在线多级聚合竞争算法
DOI：
10.1137/1.9781611974782.80
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Ohad Talmon
中科院分区：
文献类型：
--
作者：
Niv Buchbinder;Moran Feldman;J. Naor;Ohad Talmon
我们考虑 Bienkowski 等人最近研究的加权根树中的多级聚合问题。 [7]。在这个问题中，请求随着时间的推移到达树的节点，并且每个请求都指定一个截止日期。通过在截止日期之前将请求发送到根来提供服务，其成本等于从其所在节点到根的路径权重。然而，来自不同节点的请求可以被聚合并一起服务，从而节省成本。服务聚合请求集的成本等于跨越请求所在节点的子树的权重。因此，问题是找到一种有竞争力的在线聚合算法，使聚合请求的总成本最小化。这个问题在许多场景中都会自然出现，包括多播、供应链管理和传感器网络。它还与深入研究的 TCP 确认问题和在线联合补货问题有关。我们针对该问题提出了一种在线 O(D) 竞争算法，其中 D 是聚合树的深度或级别数。这一结果改进了 Bienkowski 等人最近获得的 D22D 竞争算法。 [7]。
We consider a multi-level aggregation problem in a weighted rooted tree, studied recently by Bienkowski et al. [7]. In this problem requests arrive over time at the nodes of the tree, and each request specifies a deadline. A request is served by sending it to the root before its deadline at a cost equal to the weight of the path from the node in which it resides to the root. However, requests from different nodes can be aggregated, and served together, so as to save on cost. The cost of serving an aggregated set of requests is equal to the weight of the subtree spanning the nodes in which the requests reside. Thus, the problem is to find a competitive online aggregation algorithm that minimizes the total cost of the aggregated requests. This problem arises naturally in many scenarios, including multicasting, supply-chain management and sensor networks. It is also related to the well studied TCP-acknowledgement problem and the online joint replenishment problem. We present an online O(D)-competitive algorithm for the problem, where D is the depth, or number of levels, of the aggregation tree. This result improves upon the D22D-competitive algorithm obtained recently by Bienkowski et al. [7].
影响因子：
2
作者：
Bienkowski M
通讯作者：
Bienkowski M