דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
גרגורי שוורצמן (מדעי המחשב, טכניון
event date icon
יום רביעי, 23.03.2016, 12:30
event location icon
טאוב 201
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.