Die Dozenten der Informatik-Institute der Technischen Universität Braunschweig laden im Rahmen des Informatik-Kolloquiums zu folgendem Vortrag ein:

Jukka Suomela, Helsinki Institute for Information Technology HIIT, University of Helsinki, Finland: Local algorithms and max-min linear programs

Beginn: 11.09.2008, 14:00 Uhr Ort: TU Braunschweig, Informatikzentrum, Mühlenpfordtstraße 23, 2. Obergeschoss, Raum 262A Webseite: http://www.ibr.cs.tu-bs.de/cal/kolloq/2008-09-11-suomela.html Kontakt: Prof. Dr. Sándor Fekete

A local algorithm is a distributed algorithm that completes in constant time (constant number of synchronous communication rounds), independent of the size of the network. In a local algorithm, the output of a node can only depend on the input available within its constant-radius neighbourhood; therefore a local algorithm is highly fault-tolerant, as the effect of a topology change is confined to a constant-radius part of the network.

In our work, we study local algorithms for max-min linear programs, where the objective is to

maximise w subject to Ax <= 1, Cx >= w1, x >= 0.

Here the matrices A and C are nonnegative and sparse. Each row of A has at most Delta_I positive elements, and each row C has at most Delta_K positive elements; Delta_I > 1 and Delta_K > 1 are constants.

We show that in a distributed setting, there is a sharp threshold

alpha = Delta_I (1 - 1/Delta_K)

for the local approximability of max-min linear programs. We prove that there is no local algorithm with the approximation ratio alpha. We also present a local algorithm that achieves the approximation ratio of alpha + epsilon; we can make the constant epsilon > 0 arbitrarily small at the cost of increased running time.

This is joint work with Patrik Floréen, Marja Hassinen, Joel Kaasinen, Petteri Kaski, and Topi Musto.