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: Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks

Beginn: 29.11.2010, 17:00 Uhr Ort: TU Braunschweig, Informatikzentrum, Mühlenpfordtstraße 23, 1. Obergeschoss, Raum 160 Webseite: http://www.ibr.cs.tu-bs.de/cal/kolloq/2010-11-29-suomela.html Kontakt: Prof. Dr. Sándor Fekete

In this talk I will present a distributed algorithm for finding a 2-approximation of a minimum-size vertex cover. The algorithm is fast, it is strictly local, and it can be used in anonymous networks.

A key insight in the design of the algorithm was to consider more general (and seemingly more difficult) problems:

- To improve the running time in comparison with prior work, it was useful to study minimum-weight vertex covers instead of minimum-size vertex covers.

- To apply the algorithm in anonymous networks without a port numbering, it was useful to study minimum-weight set covers instead of minimum-weight vertex covers.

This is joint work with Matti Åstrand, and it was presented at SPAA 2010; for the original publication, see http://dx.doi.org/10.1145/1810479.1810533 .