Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks

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.