CS 789 THEORY SEMINAR [home]
Speaker: Chandrashekhar Nagarajan
Title: A general approach for incremental approximation and hierarchical clustering
Date:
November 28, 2005
Abstract:
We consider the
incremental k-median problem introduced by Mettu and Plaxton and the
hierarchical median problem introduced by Plaxton which are closely related to
the well-known k-median problem. Given a metric space with facilities and
clients, the objective of the k-median problem is to select a set of k
facilities to open so as to minimize the sum of distances from the clients to
the nearest open facility. In the incremental k-median problem, we require an
ordering of facilities so that the cost of opening the first k facilities in the
ordering is "close" to the optimal solution with k facilities for all k. The
hierarchical median problem asks for solutions for all k satisfying some
"hierarchical" properties such that the cost the solution with k facilities is
"close" to the optimal k-median solution with k facilities. For these problems
the maximum ratio between the cost of the solution with k facilities and the
optimum k-median solution over all k is called the competitive ratio of the
problem.
We give a deterministic 16-competitive and and randomized 4e-competitive
algorithm for the incremental k-median problem improving the previously known
29.86-competitive algorithm by Mettu and Plaxton. We also give a deterministic
41.42-competitive and randomized 20.06-competitive algorithm for the
hierarchical median problem improving the previously known 238.8-competitive
algorithm by Plaxton. Our algorithms are based on sorting approximate solutions
for the k-median problem into buckets of geometrically increasing value and
"nesting" specific solutions to obtain the incremental solution. Our algorithmic
ideas can be generalized to give incremental algorithms for many problems like
k-MST, k-vertex cover, uncapacitated facility location problems which satisfy
certain basic properties.
This is joint work with Guolong Lin, Rajmohan Rajaraman and David P. Williamson
and will appear in SODA 2006.