Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Approximating k-Median via Pseudo-Approximation
event speaker icon
Ola Svensson (EPFL, Switzerland)
event date icon
Wednesday, 09.01.2013, 12:30
event location icon
Taub 201
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.