{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T13:31:43Z","timestamp":1753882303043,"version":"3.41.2"},"reference-count":28,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["12101594"],"award-info":[{"award-number":["12101594"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Project funded by China Postdoctoral Science Foundation","award":["2021M693337"],"award-info":[{"award-number":["2021M693337"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["12131003"],"award-info":[{"award-number":["12131003"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Beijing Natural Science Foundation","award":["Z200002"],"award-info":[{"award-number":["Z200002"]}]},{"name":"Science Foundation of the Anhui Education Department","award":["KJ2019A0834"],"award-info":[{"award-number":["KJ2019A0834"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61906062"],"award-info":[{"award-number":["61906062"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Science Foundation of Anhui Science and Technology Department","award":["1908085QF262"],"award-info":[{"award-number":["1908085QF262"]}]},{"name":"talent project of Hefei University","award":["18-19RC29"],"award-info":[{"award-number":["18-19RC29"]}]},{"name":"Guangxi Key Laboratory of Cryptography and Information Security","award":["GCIS202116"],"award-info":[{"award-number":["GCIS202116"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11901558"],"award-info":[{"award-number":["11901558"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:p> In this paper, we propose a so-called capacitated min\u2013max correlation clustering model, a natural variant of the min\u2013max 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. <\/jats:p>","DOI":"10.1142\/s0217595922400085","type":"journal-article","created":{"date-parts":[[2022,1,5]],"date-time":"2022-01-05T07:20:48Z","timestamp":1641367248000},"source":"Crossref","is-referenced-by-count":0,"title":["Approximation Algorithms for the Capacitated Min\u2013Max Correlation Clustering Problem"],"prefix":"10.1142","volume":"40","author":[{"given":"Sai","family":"Ji","sequence":"first","affiliation":[{"name":"Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun","family":"Li","sequence":"additional","affiliation":[{"name":"College of Statistics and Data Science, Beijing University of Technology, Beijing 100124, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zijun","family":"Wu","sequence":"additional","affiliation":[{"name":"Institute for Applied Optimization, School of Artificial Intelligence and Big Data, Hefei University, Hefei 230000, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yicheng","family":"Xu","sequence":"additional","affiliation":[{"name":"Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences, Shenzhen 518055, P. R. China"},{"name":"Guangxi Key Laboratory of Cryptography and Information Security, Guilin 541004, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2022,1,4]]},"reference":[{"issue":"3","key":"S0217595922400085BIB001","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1002\/sam.10012","volume":"1","author":"Achtert E","year":"2008","journal-title":"Statistical Analysis and Data Mining"},{"issue":"1","key":"S0217595922400085BIB002","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1007\/s10107-012-0565-4","volume":"141","author":"Aggarwal A","year":"2013","journal-title":"Mathematical Programming"},{"key":"S0217595922400085BIB003","first-page":"4195","volume-title":"Proc. 23rd Int. Conf. Artificial Intelligence and Statistics","author":"Ahmadian S","year":"2020"},{"key":"S0217595922400085BIB004","first-page":"61","volume-title":"Proc. Foundations of Computer Science","author":"Ahmadian S","year":"2017"},{"key":"S0217595922400085BIB005","first-page":"2237","volume-title":"Proc. 32nd Int. Conf. Machine Learning","author":"Ahn KJ","year":"2015"},{"issue":"5","key":"S0217595922400085BIB006","doi-asserted-by":"crossref","first-page":"1110","DOI":"10.1137\/110848712","volume":"41","author":"Ailon N","year":"2012","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"S0217595922400085BIB007","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1023\/B:MACH.0000033116.57574.95","volume":"56","author":"Bansal N","year":"2004","journal-title":"Machine Learning"},{"key":"S0217595922400085BIB008","first-page":"133","volume-title":"Proc. European Symp. Algorithms","author":"Bansal M","year":"2012"},{"issue":"3","key":"S0217595922400085BIB009","doi-asserted-by":"crossref","first-page":"1006","DOI":"10.1007\/s00453-018-0454-1","volume":"81","author":"Behsaz B","year":"2019","journal-title":"Algorithmica"},{"issue":"1","key":"S0217595922400085BIB010","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10115-012-0522-9","volume":"35","author":"Bonchi F","year":"2013","journal-title":"Knowledge and Information Systems"},{"issue":"4","key":"S0217595922400085BIB011","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2728170","volume":"9","author":"Bonchi F","year":"2015","journal-title":"ACM Transactions on Knowledge Discovery from Data"},{"key":"S0217595922400085BIB012","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1007\/978-3-319-59250-3_12","volume-title":"Proc. Integer Programming and Combinatorial Optimization","author":"Charikar M","year":"2017"},{"issue":"3","key":"S0217595922400085BIB013","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1016\/j.jcss.2004.10.012","volume":"71","author":"Charikar M","year":"2005","journal-title":"Journal of Computer and System Sciences"},{"key":"S0217595922400085BIB014","first-page":"219","volume-title":"Proc. 47th Annual ACM Symp. Theory of Computing","author":"Chawla S","year":"2015"},{"issue":"2","key":"S0217595922400085BIB015","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1016\/j.tcs.2006.05.008","volume":"361","author":"Demaine E","year":"2006","journal-title":"Theoretical Computer Science"},{"key":"S0217595922400085BIB016","first-page":"1167","volume-title":"Proc. Seventeenth Annual ACM-SIAM Symp. Discrete Algorithm","author":"Giotis I","year":"2006"},{"key":"S0217595922400085BIB017","first-page":"4641","volume-title":"Proc. 37th Int. Conf. Machine Learning","author":"Jafarov J","year":"2020"},{"journal-title":"Journal of Combinatorial Optimization","year":"2020","author":"Ji S","key":"S0217595922400085BIB018"},{"issue":"5","key":"S0217595922400085BIB019","doi-asserted-by":"crossref","first-page":"3065","DOI":"10.1109\/TIT.2019.2940246","volume":"66","author":"Li P","year":"2019","journal-title":"IEEE Transactions on Information Theory"},{"key":"S0217595922400085BIB020","first-page":"712","volume-title":"Proc. Twenty-First Annual ACM-SIAM Symp. Discrete Algorithm","author":"Mathieu C","year":"2010"},{"issue":"3","key":"S0217595922400085BIB021","doi-asserted-by":"crossref","first-page":"1857","DOI":"10.1137\/140994198","volume":"25","author":"Puleo GJ","year":"2015","journal-title":"SIAM Journal on Optimization"},{"issue":"6","key":"S0217595922400085BIB022","doi-asserted-by":"crossref","first-page":"4105","DOI":"10.1109\/TIT.2018.2819696","volume":"64","author":"Puleo GJ","year":"2018","journal-title":"IEEE Transactions on Information Theory"},{"issue":"2","key":"S0217595922400085BIB023","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/s10107-002-0323-0","volume":"94","author":"Ralphs TK","year":"2003","journal-title":"Mathematical Programming"},{"key":"S0217595922400085BIB024","first-page":"81:1","volume-title":"Proceedings Annual European Symp. Algorithms","author":"Saha B","year":"2019"},{"key":"S0217595922400085BIB025","first-page":"526","volume-title":"Proc. Fifteenth Annual ACM-SIAM Symp. Discrete Algorithms","author":"Swamy C","year":"2004"},{"key":"S0217595922400085BIB026","first-page":"439","volume-title":"Proc. 2018 World Wide Web Conf.","author":"Veldt N","year":"2018"},{"key":"S0217595922400085BIB027","first-page":"1868","volume-title":"Proc. 26th ACM SIGKDD Int. Conf. Knowledge Discovery & Data Mining","author":"Veldt N","year":"2020"},{"issue":"2","key":"S0217595922400085BIB028","doi-asserted-by":"crossref","first-page":"709","DOI":"10.1007\/s11081-020-09503-0","volume":"21","author":"Xu Y","year":"2020","journal-title":"Optimization and Engineering"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595922400085","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,16]],"date-time":"2023-03-16T05:53:03Z","timestamp":1678945983000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0217595922400085"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,4]]},"references-count":28,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["10.1142\/S0217595922400085"],"URL":"https:\/\/doi.org\/10.1142\/s0217595922400085","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"type":"print","value":"0217-5959"},{"type":"electronic","value":"1793-7019"}],"subject":[],"published":{"date-parts":[[2022,1,4]]},"article-number":"2240008"}}