{"id":188970,"date":"2013-01-24T00:00:00","date_gmt":"2013-01-29T09:44:21","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/approximation-algorithms-for-facility-location-problems-and-network-routing-problems\/"},"modified":"2016-08-10T07:17:34","modified_gmt":"2016-08-10T14:17:34","slug":"approximation-algorithms-for-facility-location-problems-and-network-routing-problems","status":"publish","type":"msr-video","link":"https:\/\/www.microsoft.com\/en-us\/research\/video\/approximation-algorithms-for-facility-location-problems-and-network-routing-problems\/","title":{"rendered":"Approximation Algorithms for Facility Location Problems and Network Routing Problems"},"content":{"rendered":"
\n

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.<\/p>\n

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.<\/p>\n<\/div>\n

<\/p>\n","protected":false},"excerpt":{"rendered":"

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 […]<\/p>\n","protected":false},"featured_media":197426,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr_hide_image_in_river":0,"footnotes":""},"research-area":[],"msr-video-type":[],"msr-locale":[268875],"msr-post-option":[],"msr-session-type":[],"msr-impact-theme":[],"msr-pillar":[],"msr-episode":[],"msr-research-theme":[],"class_list":["post-188970","msr-video","type-msr-video","status-publish","has-post-thumbnail","hentry","msr-locale-en_us"],"msr_download_urls":"","msr_external_url":"https:\/\/youtu.be\/0HHo7PWHcuQ","msr_secondary_video_url":"","msr_video_file":"","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/188970","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-video"}],"version-history":[{"count":0,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/188970\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/197426"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=188970"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=188970"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=188970"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=188970"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=188970"},{"taxonomy":"msr-session-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-session-type?post=188970"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=188970"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=188970"},{"taxonomy":"msr-episode","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-episode?post=188970"},{"taxonomy":"msr-research-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-theme?post=188970"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}