Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235614] of Pankaj K. Agarwal

Papers Submitted

  1. Agarwal, PK; Procopiuc, CM, Approximation algorithms for projective clustering, Journal of Algorithms, vol. 46 no. 2 (2002), pp. 115-139 [doi]
    (last updated on 2018/10/22)

    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 d-cylinders) so that the maximum width of a slab (respectively the maximum diameter of a d-cylinder) is minimized. Let w* be the smallest value so that S can be covered by k slabs (respectively d-cylinders), 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) d-cylinders 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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320