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

Math @ Duke





.......................

.......................


Publications [#235600] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Procopiuc, CM, Exact and approximation algorithms for clustering, in Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (1998), pp. 658-667
    (last updated on 2017/12/16)

    Abstract:
    In this paper we present an nO(k(1-1/d)) time algorithm for solving the k-center problem in Rd, 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(k(1-1/d)). Finally, we present a nO(k(1-1/d)) time algorithm for solving the L-capacitated k-center problem, provided that L = Ω(n/k1-1/d) or L = O(1). We conclude with a simple approximation algorithm for the L-capacitated k-center problem.

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

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