[talks] Shi Li preFPO

[Melissa M. Lawson]

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. 



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/talks/attachments/20130325/485e8ae7/attachment.htm>