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

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

event speaker icon
גרגורי שוורצמן (הרצאה סמינריונית לדוקטורט)
event date icon
יום רביעי, 15.03.2017, 15:00
event location icon
Taub 601
event speaker icon
מנחה: Prof. Keren Censor-Hillel
In this research we study computation in environments with uncertainty, specifically, the distributed and streaming environments. We adapt the local-ratio technique to the distributed and streaming environments. In doing so we achieve state of the art approximation algorithms for weighted vertex cover, weighted maximum matching and weighted maximum independent set in the distributed setting. In the semi-streaming model we improve the best known approximation ratio for maximum weighted matching. This talk will discuss two main results: a (2+epsilon) apprximation for weighted vertex cover in the distributed setting and a (2+epsilon) approximation for maximum weighted matching in the semi-streaming setting.