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


Algorithms for Environments with Uncertainty
event speaker icon
Gregory Schwartzman, Ph.D. Thesis Seminar
event date icon
Wednesday, 15.3.2017, 15:00
event location icon
Taub 601
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.
[Back to the index of events]