Approximation Algorithms for the Capacitated Min-Max Correlation Clustering Problem
文献类型：期刊论文
| 作者 | Ji, Sai1; Li, Jun2; Wu, Zijun3; Xu, Yicheng4,5 |
| 刊名 | ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH
 |
| 出版日期 | 2022-01-04 |
| 页码 | 13 |
| 关键词 | Capacitated clustering min-max correlation clustering integrality gap approximation algorithm |
| ISSN号 | 0217-5959 |
| DOI | 10.1142/S0217595922400085 |
| 英文摘要 | 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. |
| 资助项目 | 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记录号 | WOS:000848880700001 |
| 出版者 | WORLD SCIENTIFIC PUBL CO PTE LTD |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/61062]  |
| 专题 | 中国科学院数学与系统科学研究院 |
| 通讯作者 | 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. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。