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

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.

Cite this article

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

Outlines

/