Deterministic Clustering with Data Nets
Michelle Effros, Leonard J. Schulman · Electronic colloquium on computational complexity · 2004
We consider the K-clustering problem with the ‘ 2 distortion measure, also known as the problem of optimal flxed-rate vector quantizer design. We provide a deterministic approximation algorithm which works for all dimensions d and which, given a set of size n, computes in time poly(K)(d=) O(d) nloglog n+(d=) O(Kd) a solution of distortion at most 1+ times optimal. The key tool is construction of a new kind of representation called a data net. A variety of applications of this object are discussed.