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.