Approximating k-Median via Pseudo-Approximation

  • Ola Svensson | EPFL

K-median is the problem where we wish to open k facilities so as to minimize the average distance each client has to its closest opened facility. The lack of progress on this central problem compared to facility location (a close relative) is partly due to the difficulty of handling the hard constraint that at most k facilities are allowed to be opened.

In this talk we shall see that we can relax this constraint into a soft constraint with a “violation-dependent” increase in the runtime. This gives a novel point of view for addressing k-median that allows us to give an algorithm that achieves an approximation guarantee of 1+sqrt(3) improving upon the decade-old ratio of 3.

This is joint work with Shi Li.

Speaker Details

Ola Svensson is a tenure-track assistant professor at the School of Computer and communication
Sciences, EPFL, Switzerland. He received his M.Sc. from Uppsala University and his Ph.D. from Università della Svizzera italiana. His research focuses on understanding the complexity of fundamental optimization problems by both giving efficient (approximation) algorithms and lower bounds. His most recent award is a best paper award at FOCS 2011.

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks