Math @ Duke

Publications [#235424] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Procopiuc, CM, Approximation algorithms for projective clustering,
in Eleventh Annual ACMSIAM Symposium on Discrete Algorithms,
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
(2000),
pp. 538547
(last updated on 2018/10/19)
Abstract: 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 hyperstrips (resp. hypercylinders) so that the maximum width of a hyperstrip (resp., the maximum diameter of a hypercylinder) is minimized. Let w* be the smallest value so that S can be covered by k hyperstrips (resp. hypercylinders), each of width (resp. diameter) at most w*. It is NPhard 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) hyperstrips 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) hypercylinders 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*.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

