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

Math @ Duke



Publications [#355475] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Chang, HC; Munagala, K; Taylor, E; Welzl, E, Clustering under perturbation stability in near-linear time, Leibniz International Proceedings in Informatics, Lipics, vol. 182 (December, 2020) [doi]
    (last updated on 2021/05/15)

    We consider the problem of center-based clustering in low-dimensional Euclidean spaces under the perturbation stability assumption. An instance is α-stable if the underlying optimal clustering continues to remain optimal even when all pairwise distances are arbitrarily perturbed by a factor of at most α. Our main contribution is in presenting efficient exact algorithms for α-stable clustering instances whose running times depend near-linearly on the size of the data set when α ≥ 2 + √3. For k-center and k-means problems, our algorithms also achieve polynomial dependence on the number of clusters, k, when α ≥ 2 + √3 + ε for any constant ε > 0 in any fixed dimension. For k-median, our algorithms have polynomial dependence on k for α > 5 in any fixed dimension; and for α ≥ 2 + √3 in two dimensions. Our algorithms are simple, and only require applying techniques such as local search or dynamic programming to a suitably modified metric space, combined with careful choice of data structures.
ph: 919.660.2800
fax: 919.660.2821

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