David
P. Williamson
Title:
A general technique for incremental approximation and
hierarchical clustering
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, Chandra Nagarajan, and Rajmohan
Rajaraman.