Math @ Duke

Publications [#235600] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Procopiuc, CM, Exact and approximation algorithms for clustering,
in Ninth Annual ACMSIAM Symposium on Discrete Algorithms,
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
(1998),
pp. 658667
(last updated on 2017/12/16)
Abstract: In this paper we present an nO(k(11/d)) time algorithm for solving the kcenter problem in Rd, under L∞ and L2 metrics. 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(k(11/d)). Finally, we present a nO(k(11/d)) time algorithm for solving the Lcapacitated kcenter problem, provided that L = Ω(n/k11/d) or L = O(1). We conclude with a simple approximation algorithm for the Lcapacitated kcenter problem.


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

