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

The Taub Faculty of Computer Science Events and Talks

Algorithms for Environments with Uncertainty
event speaker icon
Gregory Schwartzman (Ph.D. Thesis Seminar)
event date icon
Wednesday, 15.03.2017, 15:00
event location icon
Taub 601
event speaker icon
Advisor: 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.