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