טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentSchwartzman Gregory
SubjectAlgorithms for Environments with Uncertainty
DepartmentDepartment of Computer Science
Supervisor Professor Keren Censor-Hillel
Full Thesis textFull thesis text - English Version


Abstract

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. Many of our results in the distributed setting achieve optimal running time. In the semi-streaming model we present a deterministic (2ε)-approximation algorithm for maximum weight matching. This improves upon the previous best known approximation ratio of (3.5 ε).


We also show how to apply property testing and derandomization techniques in the distributed settings. We initiate a thorough study of distributed property testing - producing algorithms for property testing problems in the CONGEST model. In particular, we present a distributed emulation technique for many sequential tests, and present distributed tests for triangle-freeness, cycle-freeness, and bipartiteness. In addition, we show a logarithmic lower bound for testing bipartiteness and cycle-freeness. We also present tools for derandomizing solutions to local problems in the Congested Clique and CONGEST model. Our techniques give a deterministic maximal independent set (MIS) algorithm in the CONGEST model running in O(Dlog2 n) rounds, where D is the diameter of the graph.