Title :
A sublinear time approximation scheme for clustering in metric spaces
Author_Institution :
Stanford Univ., CA, USA
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 ΣiΣ{u,v}⊂S(i)d(u,v). In this paper, we show an approximation scheme for this problem
Keywords :
approximation theory; computational complexity; graph theory; minimisation; pattern clustering; set theory; clustering; metric 2-clustering problem; metric spaces; minimization; set partitioning; sublinear-time approximation scheme; weighted graph; Clustering algorithms; Extraterrestrial measurements; Polynomials;
Conference_Titel :
Foundations of Computer Science, 1999. 40th Annual Symposium on
Conference_Location :
New York City, NY
Print_ISBN :
0-7695-0409-4
DOI :
10.1109/SFFCS.1999.814587
