报告题目：Approximation Algorithms on k-Correlation Clustering

报告时间：2023年12月27日（星期三）下午15:00-16:00

报告地点：沙河校区，二教110

报告人：刁卓，中央财经大学吉祥坊体育网页，副教授

报告摘要：In this talk, we consider the k-correlation clustering problem. Given an edge weighted graph G(V, E) where the edges are labeled either “+” (similar) or “−”(different) with nonnegative weights, we want to partition the nodes into at most k clusters to maximize agreements—the total weights of “+” edges within clusters and “−” edges between clusters. This problem is NP-hard. We design an approximation algorithm with the approximation ratio max{a, [(2−k)a+k−1]/k}, where a is the weighted proportion of “+” edges in all edges. As a varies from 0 to 1, the approximation ratio varies from k−1/k to 1 and the minimum value is 1/2.

报告人简介：刁卓，中央财经大学副教授，硕士研究生导师，中国科学院数学与系统科学研究院理学博士。研究方向包括图论，离散数学，网络博弈，组合优化，算法设计与分析等。主持参与两项国家自然科学基金项目。在数学和计算机科学相关领域出版学术专著两部，国内外知名期刊会议发表文章二十余篇。