关联聚类问题的半定规划舍入算法  

A semidefinite programming rounding algorithm for correlation clustering problem

作　　者：王一水 徐大川[1] 吴晨晨[2] 

机构地区：[1]北京工业大学应用数理学院,北京100124 [2]天津理工大学理学院,天津300384

出　　处：《运筹学学报》2018年第1期67-76,共10页Operations Research Transactions

基　　金：国家自然科学基金(Nos.11501412;11531014)

摘　　要：主要研究带有两类权重的一般图下的关联聚类问题.问题的定义是,给定图G=(V,E),每条边有两类权重,我们需要将点集V进行聚类,目标是最大相同性,即最大化属于某个类的边的第一类权重之和加上在两个不同类之间的边的第二类权重之和.该问题是NP-难的,我们利用外部旋转技术将现有的半定规划舍入0.75-近似算法改进.算法的分析指出,改进的算法虽然不能将近似比0.75提高,但是对于大多数实例,可以获得更好的运行效果.This paper considers the correlation clustering problem on general graphs with two types of edge weight. Given a graph G=（V,E） where each edge has two types of weight, we need to cluster the set V, subject to the objective so-called maximize agreements, that is, maximizing the total first type of weight for edges within clusters plus the total second type of weight for edges between clusters. This problem is NP-hard. We use outward rotation technique to improve the previous semidefinite programming rounding 0.75-approximation algorithm. The analysis shows that the new algorithm we provide can not improve the approximation ratio 0.75, however, it has better performance for lots of instances.

关 键 词：关联聚类问题 半定规划舍入 外部旋转 近似算法 

分 类 号：O221.7[理学—运筹学与控制论]