The Taub Faculty of Computer Science Events and Talks

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.