Exact and Approximation Algorithms for Clustering

Exact and Approximation Algorithms for Clustering

0.00 Avg rating0 Votes
Article ID: iaor20121006
Volume: 33
Issue: 2
Start Page Number: 201
End Page Number: 226
Publication Date: Jun 2002
Journal: Algorithmica
Authors: ,
Keywords: k-median
Abstract:

In this paper we present an nˆ O(k 1‐1/d ) ‐time algorithm for solving the k ‐center problem in eals 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) .

Reviews

Required fields are marked *. Your email address will not be published.