English

运筹学学报 >

2018 , Vol. 22 >Issue 1: 67 - 76

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2018.01.005

运筹学

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

展开
  • 1. 北京工业大学应用数理学院, 北京 100124; 2. 天津理工大学理学院, 天津 300384

收稿日期: 2016-06-08

  网络出版日期: 2018-03-15

基金资助

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

收起

A semidefinite programming rounding algorithm for correlation clustering problem

Expand
  • 1. College of Applied Sciences, Beijing University of Technology, Beijing 100124, China; 2. College of Science, Tianjin University of Technology, Tianjin 300384, China

Received date: 2016-06-08

  Online published: 2018-03-15

Fold

摘要

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

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

本文引用格式

王一水, 徐大川, 吴晨晨 . 关联聚类问题的半定规划舍入算法[J]. 运筹学学报, 2018 , 22(1) : 67 -76 . DOI: 10.15960/j.cnki.issn.1007-6093.2018.01.005

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

Options
文章导航

/

〈 〉