NeurIPS 2021 Spotlight | 针对有缺失坐标的聚类问题的核心集

本文是《针对有缺失坐标的聚类问题的核心集（Coresets for Clustering with Missing Values）》的解读。该工作为带有多个缺失坐标的 k-聚类问题，特别是 k-means，设计第一个有理论保证的、可在近线性时间构造的核心集（coreset)。我们的核心集可以用来加速一个最近的 SODA 2021 结果，从而得到第一个带缺失坐标k-means问题的近线性时间近似方案。本工作还提供相应的实验来证明算法的实用性。

本文被 NeurIPS 2021 接收为 Spotlight（top 3%），论文共同作者为约翰霍普金斯大学副教授 Vladimir Braverman，北京大学助理教授姜少峰，以色列魏茨曼科学研究所教授 Robert Krauthgamer 和约翰霍普金斯大学博士生吴旋。按照理论计算机科学界的习惯，论文作者按照姓氏的首字母排序。