Algorithms Seminar

Competitive Algorithms for Online Multi-level Aggregation

Speaker:Seffi Naor
Date: Thursday, January 11, 2018
Time: 12:00pm - 1:00pm
Location: D344 LSRC, Duke


We 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 that is $O(D^2)$-competitive for the problem, where $D$ is the depth of the aggregation tree. This result improves upon the $O(D^2 2^D)$-competitive algorithm obtained recently by Bienkowski et al.~\cite{BBBCDF15}.


Seffi Naor is a Professor of Computer Science at the Technion-Israel Institute of Technology. He received his PhD degree from Hebrew University in Computer Science in 1987. From 1987 to 1988, he was a postdoc fellow at the University of Southern California followed by Stanford University with the same position until 1991. From 1998 to 2000 he was at Bell Labs and from 2005 to 2007, he worked at Microsoft Research in Redmond as a visiting researcher.