ABSTRACT:
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.
BIO:
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.