静5青年讲座 | A Coreset Framework for Constrained k-Clustering
A Coreset Framework for Constrained k-Clustering
报告人
Dr. Xuan Wu, Huawei TCS Lab
时 间
2023年2月28日 星期二 16:00
地 点
静园五院204
Host
姜少峰 助理教授
Abstract
k-Clustering (e.g k-means, k-median) is the task to partition a data set into k groups of similar points. In practice, specific constraints are often imposed on the clustering task. Examples include capacitated clustering, fair clustering, robust clustering, and fault-tolerant clustering. Despite their importance, these constrained variants of clustering often do not admit a scalable solution or are even hard to approximate. To this end, we consider a data reduction technique, called coresets. An epsilon-coreset is a small subset of the input dataset such that the clustering objectives are almost the same (up to a 1+epsilon factor). In the vanilla case, coresets are a justified scalable solution for k-clustering and have been extensively studied. However, in the constrained case, our understanding of coresets is falling way behind for a long while.
In this talk, I will introduce a new coreset framework that allows us to construct improved or new coresets for a large family of constrained clustering, based on a series of my recent works. In particular, I will show how to use the framework to construct the first poly(k/epsilon)-sized epsilon-coresets for capacitated, fair, and fault-tolerant k-clustering and the first coreset of size O(m+poly(k/epsilon)) for (k,m)-robust clustering (m outliers should be excluded), in Euclidean space and other important metric spaces. Moreover, I will introduce a general approach to studying structural constraints of clustering problems and try to explore the limit of this framework.
Biography
Xuan Wu is a researcher in Huawei TCS Lab. Before joining Huawei, he obtained his Ph.D. from Johns Hopkins University. Prior to JHU, Xuan Wu earned his Master's Degree and Bachelor's Degree from IIIS and Yao Class, both at Tsinghua University.
往 期 讲 座
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。
点“阅读原文”查看海报