| 关联聚类问题的半定规划舍入算法 |
| |
| 引用本文： | 王一水,徐大川,吴晨晨.关联聚类问题的半定规划舍入算法[J].运筹学学报,2018,22(1):67-76. |
| |
| 作者姓名： | 王一水 徐大川 吴晨晨 |
| |
| 作者单位： | 1. 北京工业大学应用数理学院, 北京 100124; 2. 天津理工大学理学院, 天津 300384 |
| |
| 基金项目： | 国家自然科学基金(Nos. 11501412, 11531014) |
| |
| 摘 要： | 主要研究带有两类权重的一般图下的关联聚类问题. 问题的定义是, 给定图G=(V,E), 每条边有两类权重, 我们需要将点集V进行聚类, 目标是最大相同性, 即最大化属于某个类的边的第一类权重之和加上在两个不同类之间的边的第二类权重之和. 该问题是NP-难的, 我们利用外部旋转技术将现有的半定规划舍入0.75-近似算法改进. 算法的分析指出, 改进的算法虽然不能将近似比0.75提高, 但是对于大多数实例, 可以获得更好的运行效果.
|
| 关 键 词： | 关联聚类问题 半定规划舍入 外部旋转 近似算法 |
| 收稿时间： | 2016-06-08 |
A semidefinite programming rounding algorithm for correlation clustering problem |
| |
| WANG Yishui,XU Dachuan,WU Chenchen.A semidefinite programming rounding algorithm for correlation clustering problem[J].OR Transactions,2018,22(1):67-76. |
| |
| Authors: | WANG Yishui XU Dachuan WU Chenchen |
| |
| Institution: | 1. College of Applied Sciences, Beijing University of Technology, Beijing 100124, China; 2. College of Science, Tianjin University of Technology, Tianjin 300384, China |
| |
| Abstract: | This paper considers the correlation clustering problem on general graphs with two types of edge weight. Given a graph G=(V,E) where each edgehas 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. |
| |
| Keywords: | correlation clustering semidefinite programming rounding outward rotation approximation algorithm |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
|
