Approximation algorithms for projective clustering
We consider the following two instances of the projective clustering problem: Given a set S of n points in Rd and an integer k>0, cover S by k hyper-strips (resp. hyper-cylinders) so that the maximum width of a hyper-strip (resp., the maximum diameter of a hyper-cylinder) is minimized. Let w* be the smallest value so that S can be covered by k hyper-strips (resp. hyper-cylinders), each of width (resp. diameter) at most w*. It is NP-hard to compute k planar strips of width even at most Cw*, for any constant C>0. This paper contains four main results related to projective clustering: (i) For d = 2, we present a randomized algorithm that computes O(k log k) strips of width at most 6 w* that cover S. Its expected running time is O(nk2 log4 n) if k2 log k≤n; for larger values of k, the expected running time is O(n2/3 k8/3 log4 n). We also propose another algorithm that computes a cover of S by O(k log k) strips of width at most w* in expected running time O(n4/3k4/3 log11/3 n) if k2 log k≤n. (ii) For d = 3, a cover of S by O(k log k) hyper-strips of width at most 24 w* can be computed in expected time O(n3/2k11/4poly log n). (iii) We compute a cover of S⊂Rd by O(dk log k) hyper-cylinders of diameter at most 8 w* in expected time O(dnk3 log4 n). We also present some extensions of this result. (iv) Finally, we present an O(n log n) algorithm that covers S by two strips of width at most 3 w*.
Agarwal, PK; Procopiuc, CM
Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms
Start / End Page