Exact and approximation algorithms for clustering


Journal Article

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.

Duke Authors

Cited Authors

  • Agarwal, PK; Procopiuc, CM

Published Date

  • December 1, 1998

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Start / End Page

  • 658 - 667

Citation Source

  • Scopus