Approximation Algorithms for Facility Location Problems and Network Routing Problems

Опубликовано 8 августа 2016, 21:25

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.