Math @ Duke
|
Publications [#235442] of Pankaj K. Agarwal
Papers Published
- Agarwal, PK; Procopiuc, CM, Exact and approximation algorithms for clustering,
Algorithmica, vol. 33 no. 2
(January, 2002),
pp. 201-226, Springer Nature [doi]
(last updated on 2023/06/02)
Abstract: In this paper we present an nO(k1-1/d)-time algorithm for solving the k-center problem in ℝd, under L∞- and L2-metrics. The algorithm extends to other metrics, and to the discrete k-center problem. We also describe a simple (1 + ε)-approximation algorithm for the k-center problem, with running time O(n log k) + (k/ε)O(k1-1/d). Finally, we present an nO(k1-1/d)-time algorithm for solving the L-capacitated k-center problem, provided that L = Ω(n/k1-1/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 27708-0320
|
|