**
Polynomial Time Approximation Schemes for Geometric k-Clustering.
**

*
Rafail Ostrovsky, Yuval Rabani
*

**
Abstract:
**

The Johnson-Lindenstrauss lemma states that n points in a high dimensional Hilbert space can be embedded with small distortion of the distances into an O(\log n) dimensional space by applying a random linear transformation. We show that similar (though weaker) properties hold for certain random linear transformations over the Hamming cube. We use these transformations to solve NP-hard clustering problems in the cube as well as in geometric settings.

More specifically, we address the following clustering
problem. Given n points in a larger set (for example,
R^{d}) endowed with a distance function (for example;
L^{2} distance), we would like to partition the data set
into k disjoint clusters, each with a "cluster center",
so as to minimize the sum over all data points of the
distance between the point and the center of the cluster
containing the point. The problem is provably NP-hard in
some high dimensional geometric settings, even for k=2.
We give polynomial time approximation schemes for this
problem in several settings, including the binary cube
{0,1}^{d} with Hamming distance, and R^{d}) either
with L^{1} distance, or with L^{2} distance, or with the
square of L^{2} distance. In all these settings, the best
previous results were constant factor approximation guarantees.

We note that our problem is similar in flavor to the k-median problem (and the related facility location problem), which has been considered in graph-theoretic and fixed dimensional geometric settings, where it becomes hard when kis part of the input. In contrast, we study the problem when k is fixed, but the dimension is part of the input.

**comment:**
In JACM 49(2): 139-156 (2002).

Preliminary version in Proceedings of 41st Annual IEEE Symposium on the Foundations
of Computer Science (FOCS-2000).

An overview [power point presentation].

Fetch PostScript file of the paper Fetch PDF file of the paper

Back to the Rafail Ostrovsky publication list or to the Rafail Ostrovsky main page.