<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'>Shi Li will present his preFPO on Thursday March 28 at 1:30 PM in Room 401 (note room!).<div>The members of his committee are:  Moses Charikar, advisor; Mark Braverman and Julia </div><div>Chuzhoy (Toyota Tech Inst), readers; Zeev Dvir and Bernard Chazelle, nonreaders.  Everyone </div><div>is invited to attend his talk.  His abstract follows below.</div><div>------------------------<br><br><div style="color:#000;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt;">title : Approximation Algorithms for Facility Location and Network <br>Routing Problems<br><br>abstract :<br>My thesis is about approximation algorithms for two different classes of <br>optimization problems.<br><br>The first class is facility location problems. Two important problems in <br>this category are uncapacitated facility location and k-median, both <br>having long histories and numerous applications. We give improved <br>approximation ratios for both problems. In the first part of my talk, I <br>will focus on my recent work with Svensson (LS13) about an improved <br>approximation algorithm for k-median. Our algorithm, which gives a <br>1+sqrt(3)+eps-approximation for k-median, is based on two rather <br>surprising components. First, we show that it suffices to find an <br>\alpha-approximate solution that contains k+O(1) medians. Second, we <br>give such a pseudo-approximation algorithm with \alpha=1+sqrt(3)+eps.<br><br>The second class is network routing problems. These are an important <br>class of optimization problems, among which the Edge-Disjoint Paths <br>(EDP) problem is one of the central and most extensively studied. In <br>spite of its rich history, there is still a huge gap between the <br>sqrt(log n)-hardness of approximation. In the second part of my talk, I <br>will give an overview of my joint work with Chuzhoy (CL12), which gives <br>a poly-logarithmic approximation for EDP by slightly relaxing the <br>edge-disjointness constraint : we allow each edge in the network to be <br>used twice (i.e, we allow congestion 2). This culminates a long line of <br>research on the EDP with congestion problem.<br><br><br></div><br></div></div></body></html>