Skip to main content
Log in

Exact and Approximation Algorithms for Clustering

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

In this paper we present an n^ O(k 1-1/d ) -time algorithm for solving the k -center problem in \reals d , under L fty - and L 2 -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(nlog  k) + (k/ɛ)^ O(k 1-1/d ) . Finally, we present an n^ O(k 1-1/d ) -time algorithm for solving the L -capacitated k -center problem, provided that L=Ω(n/k 1-1/d ) or L=O(1) .

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Author information

Authors and Affiliations

Authors

Additional information

Received July 25, 2000; revised April 6, 2001.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Agarwal, P., Procopiuc, C. Exact and Approximation Algorithms for Clustering. Algorithmica 33, 201–226 (2002). https://doi.org/10.1007/s00453-001-0110-y

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-001-0110-y

Navigation