Approximating k-Median via Pseudo-Approximation

Speaker  Ola Svensson

Host  Mohit Singh

Affiliation  EPFL

Duration  00:40:45

Date recorded  18 December 2012

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.

©2012 Microsoft Corporation. All rights reserved.
> Approximating k-Median via Pseudo-Approximation