The Taub Faculty of Computer Science Events and Talks

We consider a multi-level aggregation problem in a weighted rooted tree, studied recently by Bienkowski et al. In this problem requests arrive over time at the nodes of the tree, and each request specifies a non-decreasing waiting costs. 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 consider the general case as well as a special case in which instead of waiting costs each request has a deadline for its service. We present an online $O(D)$-competitive algorithm for the deadline problem, where $D$ is the depth, or number of levels, of the aggregation tree and an online $O(D^3)$-competitive algorithm for the general problem.