Abstract:

In the problem of data aggregation in communication networks, messages arriving in the nodes of a network are to be forwarded to its root, and messages accumulated at a given intermediate node may be aggregated and forwarded together paying only a single link cost. However, messages accrue a delay penalty for waiting at a node, and the goal is to minimize the sum total of the link costs and delay penalties for a given message sequence. In an online setting, we obtain an O(log C_mst)-competitive algorithm for networks of bounded treewidth, where C_mst is the cost of the a minimum spanning tree in the network.  The result is based on a relation between the data aggregation problem and the Prize-Collecting Steiner Tree problem, and it extends to any other networks where the PCST problem can be solved efficiently or admits a fully polynomial-time approximation scheme. (Joint work with Lauri Ahlroth and André Schumacher.)