Sara complete her Ph.D. thesis Approximation Algorithms for Clustering and Facility Location Problems under the supervision of Professor Chaitanya Swamy. Facility location problems are a rich class of combinatorial optimization problems that typically involve deciding where to set up facilities so as to serve clients in the most cost-effective manner. These models are used to abstract a variety of real-world settings, such as supply-chain optimization problems, and clustering problems in data mining. Although the simplest facility location problems are quite well understood, there are various gaps in our knowledge of more sophisticated variants; Sara's research has made significant strides in devising algorithms for such problems.
Sara's thesis had three main contributions: the first local-search based approximation algorithm for the mobile facility location problem; the first polytime approximation scheme for the minimum-load k-facility location problem on line metrics; and the first approximation results for certain clustering problems with non-uniform lower bounds and outliers. These results were presented at prestigious conferences: SODA 2013, APPROX 2014, and ICALP 2016.
In additional to her doctoral thesis work with her supervisor, Sara collaborated on research projects with Professor Ola Svensson (EPFL), Professor Zachary Friggstad (University of Alberta), and Professor Laura Sanita (University of Waterloo). All these collaborations were highly successful, yielding top-notch publications in FOCS 2017, ICALP 2017, and IPCO 2016. Especially noteworthy is the FOCS 2017 paper which presented the first algorithmic improvement in over a decade on the classical k-means clustering problem.