摘要
主要研究带有两类权重的一般图下的关联聚类问题.问题的定义是,给定图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.
出处
《运筹学学报》
CSCD
北大核心
2018年第1期67-76,共10页
Operations Research Transactions
基金
国家自然科学基金(Nos.11501412
11531014)
关键词
关联聚类问题
半定规划舍入
外部旋转
近似算法
correlation clustering, semidefinite programming rounding, outward ro-tation, approximation algorithm
