A sublinear time approximation scheme for clustering in metric spaces

20 January 2003

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

p. 154-159
https://doi.org/10.1109/sffcs.1999.814587

Abstract

The metric 2-clustering problem is defined as follows: given a metric (or weighted graph) (X,d), partition X into two sets S(1) and S(2) in order to minimize the value of /spl Sigma//sub i//spl Sigma//sub {u,v}/spl sub/S(i)/d(u,v). In this paper, we show an approximation scheme for this problem.

Keywords

EXTRATERRESTRIAL MEASUREMENTS
CLUSTERING ALGORITHMS
POLYNOMIALS

This publication has 3 references indexed in Scilit:

Sublinear time algorithms for metric space problems
Published by Association for Computing Machinery (ACM) ,1999
Approximation algorithms for min-sum p-clustering
Discrete Applied Mathematics, 1998
P-Complete Approximation Problems
Journal of the ACM, 1976