# [talks] Shi Li preFPO

Melissa M. Lawson mml at CS.Princeton.EDU
Mon Mar 25 14:50:45 EDT 2013

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>