Math @ Duke

Publications [#235614] of Pankaj K. Agarwal
Papers Submitted
 Agarwal, PK; Procopiuc, CM, Approximation algorithms for projective clustering,
Journal of Algorithms, vol. 46 no. 2
(2002),
pp. 115139 [doi]
(last updated on 2018/07/22)
Abstract: We consider the following two instances of the projective clustering problem: Given a set S of n points in ℝd and an integer k > 0, cover S by k slabs (respectively dcylinders) so that the maximum width of a slab (respectively the maximum diameter of a dcylinder) is minimized. Let w* be the smallest value so that S can be covered by k slabs (respectively dcylinders), each of width (respectively diameter) at most w*. This paper contains three main results: (i) For d = 2, we present a randomized algorithm that computes O(k log k) strips of width almost w* that cover S. Its expected running time is O(nk2log4n) if k2 log k ≤ n; for larger values of k, the expected running time is O(n2/3k8/3log14/3n). (ii) For d = 3, a cover of S by O(k log k) slabs of width at most w* can be computed in expected time O(n3/2k9/4 polylog(n)). (iii) We compute a cover of S ⊂ ℝd by O(dk log k) dcylinders of diameter at most 8w* in expected time O(dnk3log4n). We also present a few extensions of this result. © 2003 Elsevier Science (USA). All rights reserved.


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

