ECCC-Report TR04-050https://eccc.weizmann.ac.il/report/2004/050Comments and Revisions published for TR04-050en-usTue, 15 Jun 2004 16:54:49 +0300
Paper TR04-050
| Deterministic clustering with data nets |
Michelle Effros,
Leonard Schulman
https://eccc.weizmann.ac.il/report/2004/050We consider the $K$-clustering problem with the $\ell_2^2$
distortion measure, also known as the problem of optimal
fixed-rate vector quantizer design. We provide a deterministic
approximation algorithm which works for all dimensions $d$ and
which, given a data set of size $n$, computes in time
${\rm poly}(K)(d/\ep)^{O(d)} n \log \log n +(d/\ep)^{O(Kd)}$
a solution of distortion at most $1+\ep$ 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.
Tue, 15 Jun 2004 16:54:49 +0300https://eccc.weizmann.ac.il/report/2004/050