Math @ Duke

Publications [#235480] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Procopiuc, CM; Varadarajan, KR, Approximation algorithms for a kline center,
Algorithmica (New York), vol. 42 no. 34
(2005),
pp. 221230 [doi]
(last updated on 2018/02/19)
Abstract: Given a set P of n points in ℝd and an integer k > 1, let w* denote the minimum value so that P can be covered by k congruent cylinders of radius w*. We describe a randomized algorithm that, given P and an ε > 0, computes k cylinders of radius (1 + ε) w* that cover P. The expected running time of the algorithm is O(n log n), with the constant of proportionality depending on k, d, and ε. We first show that there exists a small "certificate" Q ⊆ P, whose size does not depend on n, such that for any k congruent cylinders that cover Q, an expansion of these cylinders by a factor of (1 + ε) covers P. We then use a wellknown scheme based on sampling and iterated reweighting for computing the cylinders. © 2005 Springer Science+Business Media, Inc.


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

