Consider the multi-level aggregation problem in a weighted rooted tree. In this problem, requests arrive over time at the nodes of the tree. where each request specifies a deadline. A request needs to be served by sending it to the root before its deadline at a cost equal to the weight of the path from its node to the root. However, requests from different nodes can also 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 containing the requests. Thus, the problem is to find a good online aggregation scheme that minimizes the total cost of the aggregated requests. The 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 algorithm which is O(D)​​-competitive for the problem, where D​​ is the depth of the aggregation tree. This result significantly improves upon the O(D2 2D)​​-competitive algorithm recently obtained by Bienkowski et al. We extend our competitive bounds for the version where instead of deadlines the goal is to minimize the sum of delays incurred by the requests.

Joint work with Niv Buchbinder, Moran Feldman, and Ohad Talmon.