Skip to yearly menu bar Skip to main content


Poster

New and Improved Bounds on the Approximation of Complete-Link

Sanjoy Dasgupta · Eduardo Laber


Abstract:

Linkage methods such as Complete-Link are among the most popular algorithms for hierarchical clustering. Despite their relevance, the current knowledge regarding the qualityof the clustering produced by these methods is quite limited. Here, we improve the currently availablebounds on the maximum diameter of the clustering obtained by Complete-Link for metric spaces.One of our new bounds, in contrast to the existing ones, allows us to separate Complete-Link from Single-Link in terms of approximation w.r.t. to the diameter, aligning with the common perception that the former is more suitable than the latter when the goal is producing compact clusters.

Live content is unavailable. Log in and register to view live content