On August 10, 2016, Prof. Dr. Marcin Bienkowski will give a talk about "Online Algorithms for Multi-Level Aggregation" in the context of the SFB 901.
Abstract:
In the Multi-Level Aggregation Problem (MLAP), requests arrive at the nodes of an edge-weighted tree T, and have to
be served eventually. A service is defined as a subtree X of T that contains its root. This subtree X serves all requests
that are pending in the nodes of X, and the cost of this service is equal to the total weight of X. Each request also incurs
waiting cost between its arrival and service times. The objective is to minimize the total waiting cost of all requests plus
the total cost of all service subtrees. Aggregation problem for trees of arbitrary depth arise in multicasting, sensor
networks, communication in organization hierarchies, and in supply-chain management. The instances of MLAP associated with these applications are naturally online, in the sense that aggregation decisions need to be made without information about future requests.
Constant-competitive online algorithms are known for MLAP with one or two levels. However, it has been open whether
there exist constant competitive online algorithms for trees of depth more than 2. Addressing this open problem, we give
the first constant competitive online algorithm for networks of arbitrary (fixed) number of levels. The competitive ratio is
O(D4 2^D), where D is the depth of T. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines.
Joint work with Martin Böhm, Jarosław Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang and Pavel Veselý, to appear at ESA 2016.