Operations Research Transactions >
2018 , Vol. 22 >Issue 1: 67 - 76
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2018.01.005
A semidefinite programming rounding algorithm for correlation clustering problem
Received date: 2016-06-08
Online published: 2018-03-15
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.
WANG Yishui, XU Dachuan, WU Chenchen . A semidefinite programming rounding algorithm for correlation clustering problem[J]. Operations Research Transactions, 2018 , 22(1) : 67 -76 . DOI: 10.15960/j.cnki.issn.1007-6093.2018.01.005
/
| 〈 |
|
〉 |