ALMOST OPTIMAL SOLUTIONS TO k-CLUSTERING PROBLEMS.

We implement an algorithm for k-clustering for small k in fixed dimensions and report experimental results here. Although the theoretical bounds on the running time are hopeless for 1 + ∊ approximating k-clusters, we note that for dimensions 2 and 3, k-clustering is practical for small k (k ≤ 4) and simple enough shapes. For the purposes of this paper, k is a small fixed constant. [ABSTRACT FROM AUTHOR]