Approximation Algorithms for the Capacitated Min-Max Correlation Clustering Problem

被引：0

作者：

Ji, Sai ^{[1
]}

Li, Jun ^{[2
]}

Wu, Zijun ^{[3
]}

Xu, Yicheng ^{[4
,5
]}

机构：

[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

来源：

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH | 2023年 / 40卷 / 01期

基金：

中国博士后科学基金; 中国国家自然科学基金; 北京市自然科学基金;

关键词：

Capacitated clustering; min-max correlation clustering; integrality gap; approximation algorithm;

D O I：

10.1142/S0217595922400085

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页数：13

共 28 条

[1] Achtert E., 2008, STAT ANAL DATA MIN, V1, P111, DOI [DOI 10.1002/sam.10012, DOI 10.1002/SAM.10012]
[2] A 3-approximation algorithm for the facility location problem with uniform capacities
Aggarwal, Ankit
Louis, Anand
Bansal, Manisha
Garg, Naveen
Gupta, Neelima
Gupta, Shubham
Jain, Surabhi
[J]. MATHEMATICAL PROGRAMMING, 2013, 141 (1-2) : 527 - 547
[3] Ahmadian S, 2020, PR MACH LEARN RES, V108, P4195
[4] Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms
Ahmadian, Sara
Norouzi-Fard, Ashkan
Svensson, Ola
Ward, Justin
[J]. 2017 IEEE 58TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2017, : 61 - 72
[5] Ahn KJ, 2015, PR MACH LEARN RES, V37, P2237
[6] IMPROVED APPROXIMATION ALGORITHMS FOR BIPARTITE CORRELATION CLUSTERING
Ailon, Nir
Avigdor-Elgrabli, Noa
Liberty, Edo
van Zuylen, Anke
[J]. SIAM JOURNAL ON COMPUTING, 2012, 41 (05) : 1110 - 1121
[7] Bansal M, 2012, LECT NOTES COMPUT SC, V7501, P133, DOI 10.1007/978-3-642-33090-2_13
[8] Correlation clustering
Bansal, N
Blum, A
Chawla, S
[J]. MACHINE LEARNING, 2004, 56 (1-3) : 89 - 113
[9] Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median
Behsaz, Babak
Friggstad, Zachary
Salavatipour, Mohammad R.
Sivakumar, Rohit
[J]. ALGORITHMICA, 2019, 81 (03) : 1006 - 1030
[10] Chromatic Correlation Clustering
Bonchi, Francesco
Gionis, Aristides
Gullo, Francesco
Tsourakakis, Charalampos E.
Ukkonen, Antti
[J]. ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA, 2015, 9 (04) : 1 - 24

← 1 2 3 →