-
题名关联聚类问题的半定规划舍入算法
- 1
-
-
作者
王一水
徐大川
吴晨晨
-
机构
北京工业大学应用数理学院
天津理工大学理学院
-
出处
《运筹学学报》
CSCD
北大核心
2018年第1期67-76,共10页
-
基金
国家自然科学基金(Nos.11501412
11531014)
-
文摘
主要研究带有两类权重的一般图下的关联聚类问题.问题的定义是,给定图G=(V,E),每条边有两类权重,我们需要将点集V进行聚类,目标是最大相同性,即最大化属于某个类的边的第一类权重之和加上在两个不同类之间的边的第二类权重之和.该问题是NP-难的,我们利用外部旋转技术将现有的半定规划舍入0.75-近似算法改进.算法的分析指出,改进的算法虽然不能将近似比0.75提高,但是对于大多数实例,可以获得更好的运行效果.
-
关键词
关联聚类问题
半定规划舍入
外部旋转
近似算法
-
Keywords
correlation clustering, semidefinite programming rounding, outward ro-tation, approximation algorithm
-
分类号
O221.7
[理学—运筹学与控制论]
-
