当前位置: 首页 >> 学术科研 >> 学术讲座 学术讲座
龙马统数·见微知著大讲堂第59讲:Approximation Algorithms on k-Correlation Clustering
  点击次数: 次 发布时间:2023-12-20   编辑:威尼斯432888cam

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

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

报告地点:沙河校区,二教110

报告人:刁卓,威尼斯432888cam,副教授

报告摘要: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.

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

学术科研

          版权所有:威尼斯432888can(中国)有限公司-搜狗百科  
          地址:北京市昌平区沙河高教园威尼斯432888cam沙河校区1号学院楼   邮政编码:102206   电 话:(010)61776184    
          邮箱:samofcufe@cufe.edu.cn    
         

学院公众号