Class of Clustering Problems

• Random Sampling Procedure

• • Generates candidates, C, that approximate the 1-center of a set of points P with constant probability
  • Size of sample must be independent of |P| & d.
  • Size of C must be independent of |P| & d.