Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

A fast distributed (2+epsilon)-approximation for weighted vertex cover
event speaker icon
Gregory Schwartzman (M.Sc. Thesis Seminar)
event date icon
Wednesday, 02.11.2016, 14:30
event location icon
Taub 701
event speaker icon
Advisor: Prof. Keren Censor-Hillel
The field of distributed graph algorithms deals with solving graph problems in a network (graph) of independent agents while minimizing the amount of communication between nodes. One such fundamental problem is weighted vertex cover. We show a fast distributed (2+epsilon)-approximation algorithm using the local ratio method. Due to a known lower bound, the number of communication rounds our algorithm achieves is tight for all constant values of epsilon. This is a joint work with Keren Censor-Hillel and Reuven Bar-Yehuda.