Improved Analysis of Complete-Linkage Clustering

Complete-linkage clustering is a very popular method for computing hierarchical clusterings in practice, which is not fully understood theoretically. Given a finite set  P ⊆ R d of points, the complete-linkage method starts with each point from  P in a cluster of its own and then iteratively merges...

Full description

Saved in:
Bibliographic Details
Published in:Algorithmica 2017-08, Vol.78 (4), p.1131-1150
Main Authors: Großwendt, Anna, Röglin, Heiko
Format: Article
Language:English
Subjects:
Algorithm Analysis and Problem Complexity
Algorithms
Approximation
Clustering
Clusters
Computer Science
Computer Systems Organization and Communication Networks
Data Structures and Information Theory
Mathematics of Computing
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Complete-linkage clustering is a very popular method for computing hierarchical clusterings in practice, which is not fully understood theoretically. Given a finite set  P ⊆ R d of points, the complete-linkage method starts with each point from  P in a cluster of its own and then iteratively merges two clusters from the current clustering that have the smallest diameter when merged into a single cluster. We study the problem of partitioning  P into  k clusters such that the largest diameter of the clusters is minimized and we prove that the complete-linkage method computes an  O (1)-approximation for this problem for any metric that is induced by a norm, assuming that the dimension  d is a constant. This improves the best previously known bound of  O ( log k ) due to Ackermann et al. (Algorithmica 69(1):184–215, 2014 ). Our improved bound also carries over to the k -center and the discrete k -center problem.
ISSN:0178-4617
1432-0541
DOI:10.1007/s00453-017-0284-6