
Speaker Shi Li Host Kostya Makarychev Affiliation Princeton University 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 kmedian. 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 kmedian. 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)+epsapproximation for kmedian, is based on two rather surprising components. First, we show that in order to given an alphaapproximation algorithm for kmedian, it suffices to give a pseudoapproximation algorithm that finds an alphaapproximate solution by opening k+O(1) facilities. Second, we give such a pseudoapproximation 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 EdgeDisjoint Paths (EDP) problem is one of the central and most extensively studied. Here, we are given k sourcesink pairs in a network and want to connect as many pairs as possible using edgedisjoint 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 polylogarithmic approximation for EDP by slightly relaxing the edgedisjointness 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.
