Informatik, TU Wien

A distributed algorithm for Vertex Cover based on the Local-Ratio technique

I will start with algorithms for approximating the minimum Vertex Cover of a graph.


I will start with algorithms for approximating the minimum Vertex Cover of a graph.  Two 2-approximate algorithms will be presented: the Greedy algorithm for the unweighted case and the Local-Ratio algorithm for the weighted case. 

The LOCAL model for distributed computation will be defined.  The challenge of extending the Local-Ratio algorithm to a distributed LOCAL algorithm will be discussed.  I will present the distributed algorithm of Bar-Yehuda et al. [PODC 2016] that computes a (2+eps)-approximation in (log Delta)/(eps log log Delta) rounds.


Guy Even received his B.Sc. degree in 1988 in Mathematics and Computer Science from the Hebrew University. Received his M.Sc. and D.Sc. in Computer Science from the Technion in 1991 and 1994, respectively. Dr. Even spent his post-doctorate in the University of the Saarland during 1995–1997 with Prof. Wolfgang Paul. Since 1997, he is a faculty member in the School of Electrical Engineering in Tel-Aviv University. Dr. Even is interested in algorithms and their applications in various fields. He has published papers on the theory of VLSI, approximation algorithms, computer arithmetic, online algorithms, frequency assignment, scheduling, packet-routing, linear-programming decoding of LDPC codes, and rateless codes. He is on the editorial board of "Theory of Computing Systems".  Together with Moti Medina, Dr. Even wrote a digital hardware textbook titled "Digital Logic Design: A Rigorous Approach" published in 2012 by Cambridge University Press.


The lecture series on research talks by the visiting professors of the PhD School can also be credited as an elective course for students of master programs of computer science.