2025年11月24日，丹麦皇家科学和文学院院士、丹麦哥本哈根大学教授Mikkel Thorup做客抖音网红黑料
交叉信息院，带来题为“兼顾速度与质量的关系聚类（Fast and Good Correlation Clustering）”特邀报告。交叉信息院副教授段然主持讲座。师生齐聚FIT楼1-222会议室，聆听讲座。
关系聚类（Correlation Clustering ）是一个在图论、机器学习和数据挖掘中有很多应用的重要问题。但其精确求解是 NP 难的，因此研究重点长期聚焦于近似算法上。近十年来，近似比由最初的超过1万，逐渐减小到小于2。然而现有算法大多需要高阶多项式复杂度。在本次讲座中，Thorup教授展示了他们研究团队的两项加速求解的核心进展。第一个成果展示了一个精巧的局部搜索算法，将纯组合方法的运行时间降到线性以下。第二个成果提出了一个具有指数个变量，但能在次线性时间近似求解的线性规划。
讲座期间，师生在Thorup教授引导下深入思考。2021级博士生尹龙晖表示：“Thorup教授为我们讲述了他们工作组在关系聚类问题上的最新进展。聚类问题是无监督机器学习中的一类基础问题，要求对一系列有特定关系的对象按关系的紧密程度进行分类。在线性规划问题中，通过改造之前的线性规划问题中的约束条件和目标函数形式，他们能以更短的时间求出同样近似程度的解。讲座给我带来了一定启发。”
2023级硕士生王少文表示：“虽然我平时的研究主要聚焦于深度学习与大模型，此前并未深入涉猎关系聚类这一具体的图论算法方向，但Thorup教授的讲解令人印象深刻。他将复杂的组合优化技巧和线性规划演进讲解得深入浅出，逻辑极其清晰。这次讲座不仅让我跨越领域的隔阂，看懂了从局部搜索到ClusterLP的技术突破，更让我久违地领略到了经典算法理论那严谨而简洁的数学之美。Thorup教授身上那种对基础科学的纯粹热爱与大家风范，让我深受感染。”
在座还包括墨尔本大学讲师王涵之，她表示：“Correlation Clustering是理论研究和应用场景中都关注的一类问题，Mikkel在报告中概述了Correlation Clustering的研究进展，讲解了基于局部搜索（local search）和基于LP的两类代表性研究方法，并对高效算法设计中算法理论结果和算法实用性间的协调问题给出了很多个人思考，令人收获颇丰。”
最后，Thorup教授总结说，这是一个非常技术性的讲座，但其中涉及的技术可能会在其他图论或机器学习问题中具有巨大的应用空间。
嘉宾介绍
Mikkel Thorup于1993年获得牛津大学的D.Phil.学位。自2013年以来，他在哥本哈根大学担任教授。2017年起，他成为VILLUM Investigator，领导哥本哈根基础算法研究中心（BARC）。Mikkel是ACM和AT&T的会士，也是丹麦皇家科学和文学院院士。他获得了2011年MAA Robbins奖数学奖，以及2015年的Villum Kann Rasmussen技术与科学研究奖，这是丹麦最高的个人研究奖项。他还获得了AMS-MOS Fulkerson奖和ACM STOC 时间检验奖。他的主要研究方向是算法与数据结构，近期的主要研究领域是哈希函数，致力于将理论与实践统一起来。
图文｜姜月亮
编辑｜吕厦敏
审核｜马雄峰
