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

doi:10.15960/j.cnki.issn.1007-6093.2018.01.005

Operations Research Transactions ›› 2018, Vol. 22 ›› Issue (1): 67-76.doi: 10.15960/j.cnki.issn.1007-6093.2018.01.005

Previous Articles Next Articles

A semidefinite programming rounding algorithm for correlation clustering problem

WANG Yishui¹XU Dachuan^1,*WU Chenchen²

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

Abstract

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

WANG Yishui, XU Dachuan, WU Chenchen. A semidefinite programming rounding algorithm for correlation clustering problem[J]. Operations Research Transactions, 2018, 22(1): 67-76.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.ort.shu.edu.cn/EN/10.15960/j.cnki.issn.1007-6093.2018.01.005

https://www.ort.shu.edu.cn/EN/Y2018/V22/I1/67

[1]	WU Hongyi, WANG Dong, WAN Long, LUO Wenchang. Approximation algorithm for mixed batch parallel machine scheduling with nested processing set restrictions [J]. Operations Research Transactions, 2026, 30(1): 188-196.
[2]	Yuan YUAN, Yan LAN, Xin HAN. A survey of scheduling with maintenance periods [J]. Operations Research Transactions, 2025, 29(1): 1-18.
[3]	Jie GAO, Juan ZOU, Yukang SUI, Yuzhong ZHANG. Unrelated parallel-machine scheduling with deteriorating maintenance activities and job rejection [J]. Operations Research Transactions, 2023, 27(3): 137-149.
[4]	An ZHANG, Yong CHEN, Guangting CHEN, Zhanwen CHEN, Qiaojun SHU, Guohui LIN. Maximum matching based approximation algorithms for precedence constrained scheduling problems [J]. Operations Research Transactions, 2022, 26(3): 57-74.
[5]	Dong WANG, Ganggang LI, Wenchang LUO. Approximation algorithm for mixed batch scheduling on identical machines for jobs with arbitrary sizes [J]. Operations Research Transactions, 2022, 26(3): 133-142.
[6]	Chunyan BI, Long WAN, Wenchang LUO. Approximation algorithm for uniform parallel machine scheduling with release dates and job rejection [J]. Operations Research Transactions, 2022, 26(2): 73-82.
[7]	Jianping LI, Lijian CAI, Junran LICHEN, Pengxiang PAN. The constrained multi-sources eccentricity augmentation problems [J]. Operations Research Transactions, 2022, 26(1): 60-68.
[8]	Hua CHEN, Guochuan ZHANG. A survey on approximation algorithms for one dimensional bin packing [J]. Operations Research Transactions, 2022, 26(1): 69-84.
[9]	Wenjie LIU, Dongmei ZHANG, Peng ZHANG, Juan ZOU. The seeding algorithm for $\mu$-similar Bregman divergences $k$-means problem with penalties [J]. Operations Research Transactions, 2022, 26(1): 99-112.
[10]	Jiachen JU, Qian LIU, Zhao ZHANG, Yang ZHOU. A local search analysis for the uniform capacitated $k$-means problem with penalty [J]. Operations Research Transactions, 2022, 26(1): 113-124.
[11]	Xiaowei LI, Xiayan CHENG, Rongheng LI. An approximation algorithm for Robust k-product facility location problem with linear penalties [J]. Operations Research Transactions, 2021, 25(4): 31-44.
[12]	Xiaoguang BAO, Chao LU, Dongmei HUANG, Wei YU. Approximation algorithm for min-max cycle cover problem on a mixed graph [J]. Operations Research Transactions, 2021, 25(1): 107-113.
[13]	Jianfeng REN, Xiaoyun TIAN. Squared metric facility location problem with outliers [J]. Operations Research Transactions, 2021, 25(1): 114-122.
[14]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[15]	LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139.

A semidefinite programming rounding algorithm for correlation clustering problem

PDF

Knowledge

Abstract

Cite this article

share this article

Related Articles 15

Recommended Articles

Metrics

Comments