Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Approximation Algorithms for Facility Location Problems and Network Routing Problems

Speaker  Shi Li

Affiliation  Princeton University

Host  Kostya Makarychev

Duration  00:52:49

Date recorded  24 January 2013

In this talk, I will talk about two broad themes of my research. The first theme in my research is facility location problems. Two important problems in this category are uncapacitated facility location and k-median. Both problems have long histories and numerous applications. In the first part of my talk, I will focus on my recent work with Svensson about an improved approximation algorithm for k-median. Here, we are given a set of potential facility locations and clients, with a distance function on these points. The goal is to open k facilities so as to minimize the sum of distances from all clients to their nearest open facilities. Our algorithm, which gives a 1+sqrt(3)+eps-approximation for k-median, is based on two rather surprising components. First, we show that in order to given an alpha-approximation algorithm for k-median, it suffices to give a pseudo-approximation algorithm that finds an alpha-approximate solution by opening k+O(1) facilities. Second, we give such a pseudo-approximation algorithm with alpha = 1+sqrt(3)+eps.

The second theme 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. Here, we are given k source-sink pairs in a network and want to connect as many pairs as possible using edge-disjoint paths. In spite of its rich history, there is still a huge gap between the sqrt(log n)-hardness of approximation and the sqrt(n)-approximation ratio for the problem. In the second part of my talk, I will give an overview of my joint work with Chuzhoy, 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.

©2013 Microsoft Corporation. All rights reserved.
> Approximation Algorithms for Facility Location Problems and Network Routing Problems