Approximation Algorithms for the Capacitated Min–Max Correlation Clustering Problem

Sai Ji (), Jun Li (), Zijun Wu and Yicheng Xu
Additional contact information
Sai Ji: Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, P. R. China
Jun Li: College of Statistics and Data Science, Beijing University of Technology, Beijing 100124, P. R. China
Zijun Wu: Institute for Applied Optimization, School of Artificial Intelligence and Big Data, Hefei University, Hefei 230000, P. R. China
Yicheng Xu: Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences, Shenzhen 518055, P. R. China5Guangxi Key Laboratory of Cryptography and Information Security, Guilin 541004, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2023, vol. 40, issue 01, 1-13

Abstract: 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.

Keywords: Capacitated clustering; min–max correlation clustering; integrality gap; approximation algorithm (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595922400085
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:40:y:2023:i:01:n:s0217595922400085

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595922400085

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().