[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
My thesis is about approximation algorithms for two different classes of
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...
More information about the talks