ECCC-Report TR99-035https://eccc.weizmann.ac.il/report/1999/035Comments and Revisions published for TR99-035en-usWed, 15 Sep 1999 16:34:38 +0200
Paper TR99-035
| Clustering for Edge-Cost Minimization |
Leonard Schulman
https://eccc.weizmann.ac.il/report/1999/035
We address the problem of partitioning a set of $n$ points into
clusters, so as to minimize the sum, over all intracluster pairs of
points, of the cost associated with each pair. We obtain a randomized
approximation algorithm for this problem, for the cost functions
$\ell_2^2,\ell_1$ and $\ell_2$, as well as any cost function
isometrically embeddable in $\ell_2^2$.
The maximization problem (maximize the costs of intercluster edges) is
approximated with high probability to within multiplicative factor
$(1-\ep)$; while the minimization problem either receives a
multiplicative $1+\ep$ approximation, or else the optimal clustering
is correctly identified except for a mislabelling of an $\ep$ fraction
of the point set. Given a fixed approximation parameter $\ep$, the
runtime is linear in $n$ for $\ell_2^2$ problems of dimension
$o(\log n / \log \log n)$; and $n^{O(\log \log n)}$ in the general
case.
The case $\ell_2^2$ is addressed by combining three elements: (a)
Variable-probability sampling of the given points, to reduce the size
of the data set. (b) Near-isometric dimension reduction. (c) A
deterministic exact algorithm which runs in time exponential in the
dimension (rather than the number of points). The remaining cases are
addressed by reduction to $\ell_2^2$.
Wed, 15 Sep 1999 16:34:38 +0200https://eccc.weizmann.ac.il/report/1999/035