Approximation Algorithms for the Capacitated Min-Max Correlation Clustering Problem

doi:10.1142/S0217595922400085

CSpace

	Approximation Algorithms for the Capacitated Min-Max Correlation Clustering Problem
	Ji, Sai 1; Li, Jun 2; Wu, Zijun 3; Xu, Yicheng 4,5
	2022-01-04
发表期刊	ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH
ISSN	0217-5959
页码	13
摘要	In this paper, we propose a so-called capacitated min-max correlation clustering model, a natural variant of the min-max correlation clustering problem. As our main contribution, we present an integer programming and its integrality gap analysis for the proposed model. Furthermore, we provide two approximation algorithms for the model, one of which is a bi-criteria approximation algorithm and the other is based on LP-rounding technique.
关键词	Capacitated clustering min-max correlation clustering integrality gap approximation algorithm
DOI	10.1142/S0217595922400085
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[12101594] ; National Natural Science Foundation of China[12131003] ; National Natural Science Foundation of China[61906062] ; National Natural Science Foundation of China[11901558] ; China Postdoctoral Science Foundation[2021M693337] ; Beijing Natural Science Foundation Project[Z200002] ; Science Foundation the Anhui Education Department[KJ2019A0834] ; Science Foundation of Anhui Science and Technology Department[1908085QF262] ; talent project of Hefei University[18-19RC29] ; Guangxi Key Laboratory of Cryptography and Information Security[GCIS202116]
WOS研究方向	Operations Research & Management Science
WOS类目	Operations Research & Management Science
WOS记录号	WOS:000848880700001
出版者	WORLD SCIENTIFIC PUBL CO PTE LTD
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/61063
专题	中国科学院数学与系统科学研究院
通讯作者	Wu, Zijun
作者单位	1.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China 2.Beijing Univ Technol, Coll Stat & Data Sci, Beijing 100124, Peoples R China 3.Hefei Univ, Sch Artificial Intelligence & Big Data, Inst Appl Optimizat, Hefei 230000, Peoples R China 4.Chinese Acad Sci, Shenzhen Inst Adv Technol, Shenzhen 518055, Peoples R China 5.Guangxi Key Lab Cryptog & Informat Secur, Guilin 541004, Peoples R China
推荐引用方式 GB/T 7714	Ji, Sai,Li, Jun,Wu, Zijun,et al. Approximation Algorithms for the Capacitated Min-Max Correlation Clustering Problem[J]. ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH,2022:13.
APA	Ji, Sai,Li, Jun,Wu, Zijun,&Xu, Yicheng.(2022).Approximation Algorithms for the Capacitated Min-Max Correlation Clustering Problem.ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH,13.
MLA	Ji, Sai,et al."Approximation Algorithms for the Capacitated Min-Max Correlation Clustering Problem".ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH (2022):13.