English

运筹学学报

• 运筹学 • 上一篇    下一篇

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

王一水1  徐大川1,* 吴晨晨2   

  1. 1. 北京工业大学应用数理学院, 北京 100124; 2. 天津理工大学理学院, 天津 300384
  • 收稿日期:2016-06-08 出版日期:2018-03-15 发布日期:2018-03-15
  • 通讯作者: 徐大川 E-mail: xudc@bjut.edu.cn
  • 基金资助:

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

A semidefinite programming rounding algorithm for correlation clustering problem

WANG Yishui1  XU Dachuan1,* WU Chenchen2   

  1. 1. College of Applied Sciences, Beijing University of Technology, Beijing 100124, China; 2. College of Science, Tianjin University of Technology, Tianjin 300384, China
  • Received:2016-06-08 Online:2018-03-15 Published:2018-03-15

PDF

327

摘要：

主要研究带有两类权重的一般图下的关联聚类问题. 问题的定义是, 给定图G=(V,E), 每条边有两类权重, 我们需要将点集V进行聚类, 目标是最大相同性, 即最大化属于某个类的边的第一类权重之和加上在两个不同类之间的边的第二类权重之和. 该问题是NP-难的, 我们利用外部旋转技术将现有的半定规划舍入0.75-近似算法改进. 算法的分析指出, 改进的算法虽然不能将近似比0.75提高, 但是对于大多数实例, 可以获得更好的运行效果.

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

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 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.

Key words: correlation clustering, semidefinite programming rounding, outward rotation, approximation algorithm