# Events

## Talk given by Prof. Dr. Marcin Bienkowski (University of Wroclaw)

Begin: Wed, 10. of Aug 2016 ( 2:00 PM)Location: Fürstenallee 11, Raum F1.110

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(D^{^4}
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.