16 Oct 10:15 Jukka Suomela: Local approximation algorithms for vertex cover

HIIT seminar, Friday Oct 16, 10:15 a.m. (coffee from 10), Exactum D122

Dr. Jukka Suomela
Helsinki Institute for Information Technology HIIT Department of Computer Science University of Helsinki

Local approximation algorithms for vertex cover

Abstract:
I will present two distributed 2-approximation algorithms for the vertex cover problem. The algorithms are strictly local in the sense that the running time (number of synchronous communication rounds) does not depend on the size of the network, but only on the maximum node degree. The algorithms are deterministic; hence they can also be converted into efficient self-stabilising algorithms.

I will focus on some key ideas in the design of these distributed algorithms. In the derivation of a mathematical proof, a classical yet seemingly counter-intuitive proof technique is making the claim more general. At first sight, a stronger claim should be harder to prove, but it often happens that, e.g., strengthening the inductive hypothesis may simplify a proof by induction. The two distributed algorithms that I present illustrate a similar principle in the design of algorithms.
The first algorithm was designed for a simpler problem, vertex cover in unweighted graphs, and hence we ruled out approaches that seemed to lead to weighted subproblems. The second algorithm was designed for a seemingly more difficult problem, vertex cover in weighted graphs; however, as a by-product we obtained a faster algorithm for the unweighted case.

This is joint work with Matti Åstrand, Patrik Floréen, Valentin Polishchuk, Joel Rybicki, and Jara Uitto. In part based on
http://dx.doi.org/10.1007/978-3-642-04355-0_21