报告题目：Efficient Constrained K-center Clustering with Background Knowledge

报告人：郭龙坤教授，福州大学

报告时间：2024年6月3日（周一）8:30

报告地点：20-200

报告摘要：Center-based clustering has attracted significant research interest from both theory and practice. In many practical applications, input data often contain background knowledge that can be used to improve clustering results. In this work, we build on widely adopted $k$-center clustering and model its input background knowledge as must-link (ML) and cannot-link (CL) constraint sets. However, most clustering problems including $k$-center are inherently NP-hard, while the more complex constrained variants are known to suffer severer approximation and computation barriers that significantly limit their applicability. By employing a suite of techniques including reverse dominating sets, linear programming (LP) integral polyhedron, and LP duality, we arrive at the first efficient approximation algorithm for constrained $k$-center with the best possible ratio of 2. We also construct competitive baseline algorithms and empirically evaluate our approximation algorithm against them on a variety of real datasets. The results validate our theoretical findings and demonstrate the great advantages of our algorithm in terms of clustering cost, clustering quality, and running time.

报告人简介：郭龙坤，福州大学数学与统计学院教授，博士生导师。数学规划学会青年理事，CCF理论计算机专委执行委员。2005与2011年分别毕业于中国科学技术大学计算机科学与技术系获工学学士与博士学位。2015年--2016年阿德莱德大学计算机学院研究工作（Research Associate）。主要研究边缘与移动网络、分布式与云计算等场景中的组合优化问题的算法设计与分析。至今共发表国内外主流学术期刊与会议论文100余篇，包括IEEE Transactions on Mobile Computing(TMC), IEEE Transactions on Computers(TC)，Algorithmica, IEEE Transactions on Parallel and Distributed Systems (TPDS), Theoretical Computer Science, Journal of Combinatorial Optimization等国际期刊及IEEE ICDCS、ACM SPAA、AAAI, IJCAI等国际会议。主持两项国家自然科学基金面上项目与一项国家自然科学基金青年项目；主持四项省部级基金（包括一项教育部博士点基金）；作为主要骨干人员参加多项国家与省部级自然科学基金。