Exact and approximation algorithms for clustering

Published

Journal Article

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).

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Procopiuc, CM

Published Date

  • January 1, 2002

Published In

Volume / Issue

  • 33 / 2

Start / End Page

  • 201 - 226

International Standard Serial Number (ISSN)

  • 0178-4617

Digital Object Identifier (DOI)

  • 10.1007/s00453-001-0110-y

Citation Source

  • Scopus