conftrace_

2020 NeurIPS NeurIPS 2020

Improved Guarantees for k-means++ and k-means++ Parallel

Abstract

In this paper, we study k-means++ and k-means||, the two most popular algorithms for the classic k-means clustering problem. We provide novel analyses and show improved approximation and bi-criteria approximation guarantees for k-means++ and k-means||. Our results give a better theoretical justification for why these algorithms perform extremely well in practice.

Authors

Konstantin Makarychev, Aravind Reddy, Liren Shan

Topics

Machine Learning > Core Methods > Clustering Machine Learning > Optimization & Theory > Optimization

Keywords

cluster analysis k-means clustering clustering algorithm approximation algorithm bicriteria approximation

More from NeurIPS 2020

All NeurIPS 2020 papers →

Bayesian Meta-Learning for the Few-Shot Setting via Deep Kernels

Skeleton-bridged Point Completion: From Global Inference to Local Adjustment

Compressing Images by Encoding Their Latent Representations with Relative Entropy Coding

Sparse Spectrum Warped Input Measures for Nonstationary Kernel Learning

An Efficient Adversarial Attack for Tree Ensembles

Learning Continuous System Dynamics from Irregularly-Sampled Partial Observations