Math @ Duke

Publications [#235442] of Pankaj K. Agarwal
Papers Submitted
 Agarwal, PK; Procopiuc, CM, Exact and Approximation Algorithms for Clustering,
Algorithmica, vol. 33 no. 2
(2002),
pp. 201226 [doi]
(last updated on 2018/11/15)
Abstract: In this paper we present an nO(k11/d)time algorithm for solving the kcenter problem in ℝd, under L∞ and L2metrics. The algorithm extends to other metrics, and to the discrete kcenter problem. We also describe a simple (1 + ε)approximation algorithm for the kcenter problem, with running time O(n log k) + (k/ε)O(k11/d). Finally, we present an nO(k11/d)time algorithm for solving the Lcapacitated kcenter problem, provided that L = Ω(n/k11/d) or L = O(1).


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

