Search for: All records

We give an algorithm for Centroid-Linkage Hierarchical Agglomerative Clustering (HAC), which computes a $$c$$-approximate clustering in roughly $$n^{1+O(1/c^2)}$$ time. We obtain our result by combining a new Centroid-Linkage HAC algorithm with a novel fully dynamic data structure for nearest neighbor search which works under adaptive updates. We also evaluate our algorithm empirically. By leveraging a state-of-the-art nearest-neighbor search library, we obtain a fast and accurate Centroid-Linkage HAC algorithm. Compared to an existing state-of-the-art exact baseline, our implementation maintains the clustering quality while delivering up to a $$36\times$$ speedup due to performing fewer distance comparisons. 

The current-best approximation algorithms for k-median rely on first obtaining a structured fractional solution known as a bi-point solution, and then rounding it to an integer solution. We improve this second step by unifying and refining previous approaches. We describe a hierarchy of increasingly-complex partitioning schemes for the facilities, along with corresponding sets of algorithms and factor-revealing non-linear programs. We prove that the third layer of this hierarchy is a 2.613-approximation, improving upon the current-best ratio of 2.675, while no layer can be proved better than 2.588 under the proposed analysis. On the negative side, we give a family of bi-point solutions which cannot be approximated better than the square root of the golden ratio, even if allowed to open k + o(k) facilities. This gives a barrier to current approaches for obtaining an approximation better than approximately 2.544. Altogether we reduce the approximation gap of bi-point solutions by two thirds.