Technische Universität Braunschweig
Institute für Informatik
Einladung zum
Informatik-Kolloquium
Jukka Suomela:
Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks
| Speaker Affiliation | Helsinki Institute for Information Technology HIIT |
| Start | 29.11.2010, 17:00 Uhr |
| Location | TU Braunschweig, Informatikzentrum, Mühlenpfordtstraße 23, 1. Obergeschoss, Raum 160 |
| Invited by | 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. |
Die Dozenten der Informatik
