第五十八期

报告人：Di Yue, University of Toronto

时间：5月15日（星期五）3:00pm

地点：静园五院204

Host：李鸣宇，图灵班2023级

报告信息

 Title

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics

 Abstract

In the metric  -median problem we are given a finite metric space  and the objective is to compute a set of  centers   that minimizes . In general metric spaces, the best polynomial time algorithm, which is due to Cohen-Addad, Grandoni, Lee, Schwiegelshohn, and Svensson, computes a -approximation for arbitrary constant . However, if the metric space has bounded doubling dimension, a near linear time  -approximation algorithm is known due to the work of Cohen-Addad, Feldmann, and Saulpic.

In this paper, we show that the -approximation algorithm can be generalized to the case when either  or  has bounded doubling dimension (but the other set not). The case when  has bounded doubling dimension is motivated by the assumption that even though  is part of a high-dimensional space, it may be that it is close to a low-dimensional structure. The case when  has bounded doubling dimension is perhaps more natural. It is motivated by specific clustering problems where the centers are low-dimensional. Specifically, our work in this setting implies the first near linear time approximation algorithm for the -median problem under discrete Fréchet distance when   is constant.

In order to solve the case when   has a bounded doubling dimension, we introduce a form of dimension reduction that replaces points from  by sets of points in . 

To solve the case when  has a bounded doubling dimension, we generalize Talwar's decomposition of doubling metrics to our setting. The running time of our algorithms is  where  and where  is the doubling dimension of  (resp.\  ). 

The results also extend to the metric (uncapacitated) facility location problem. We believe that our techniques are likely applicable to other problems. 

Based on the joint work with Anne Driemel, Jan Höckendorff, Ioannis Psarros and Christian Sohler.

 Biography

Di Yue is an incoming PhD student in the theory group at University of Toronto, advised by Aleksandar Nikolov. Previously, he obtained his BS degree from Peking University in 2025. His research interest lies in theoretical computer science, with current focus on discrepancy theory. He is also interested in computational problems related to metric spaces and high-dimensional geometry.

about CS Peer Talk

作为活动的发起人，我们来自北京大学图灵班科研活动委员会，主要由图灵班各年级同学组成。我们希望搭建一个CS同学交流的平台，促进同学间的交流合作，帮助同学练习展示，同时增进友谊。

目前在计划中的系列包括但不限于：

教程系列：学生讲者为主，介绍自己的研究领域

研究系列：学生讲者为主，介绍自己的研究成果

客座系列：邀请老师做主题报告

除非报告人特别要求，报告默认是非公开的，希望营造一个自由放松但又互相激励的交流氛围。

主讲嘉宾招募

如果你愿意和大家分享你的学术成果、经历经验，总结回顾、触发新思，欢迎报名自荐。

主讲人报名：发邮件至 [email protected]，并抄送 [email protected]，写明想讲的题目、内容及时间。