Sublinear time approximate clustering

Clustering is of central importance in a number of disciplines including Machine Learning, Statistics, and Data Mining. This paper has two foci: (1) It describes how existing algorithms for clustering can benefit from simple sampling techniques arising from work in statistics Pol84. (2) It motivates and introduces a new model of clustering that is in the spirit of the PAC (probably approximately correct) learning model, and gives examples of efficient PAC-clustering algorithms.