Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Approximating k-Median via Pseudo-Approximation

Speaker  Ola Svensson

Affiliation  EPFL

Host  Mohit Singh

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