Approximation Algorithms for Facility Location Problems and Network Routing Problems
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.
Other Videos By Microsoft Research
2016-08-08 | So You Think Quantum Computing Is Bunk? |
2016-08-08 | Power and Reliability in Extreme Scale Computing |
2016-08-08 | Compressed Sensing and Natural Image Statistics |
2016-08-08 | Making Big Data Analytics Interactive and Real-Time |
2016-08-08 | MSPAC Lunch w/John Wood - Room to Read |
2016-08-08 | Optimizing Trade-offs for Scalable Machine Learning |
2016-08-08 | Reasoning About Client Side Web Programs |
2016-08-08 | Prior Robust Optimization |
2016-08-08 | Reflections on Anonymous |
2016-08-08 | Building a Better Anonymous |
2016-08-08 | Approximation Algorithms for Facility Location Problems and Network Routing Problems |
2016-08-08 | Product Club |
2016-08-08 | Mime/Dance |
2016-08-08 | The Globalization of Sumo |
2016-08-08 | My Little Pony or Porn Star |
2016-08-08 | To Bot or Not |
2016-08-08 | Pew Data, Challenges and Opportunities |
2016-08-08 | Robustness and Optimization of Scrip Systems |
2016-08-08 | Intros and proposed talks from all attendees |
2016-08-08 | Provable Bounds in Machine Learning |
2016-08-08 | Windows Phone Garage: Building Awesome Apps |