{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T13:05:19Z","timestamp":1753880719612,"version":"3.41.2"},"reference-count":30,"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":["11971349"],"award-info":[{"award-number":["11971349"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11201333"],"award-info":[{"award-number":["11201333"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11201333"],"award-info":[{"award-number":["11201333"]}],"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> Clustering is one of the most important problems in the fields of data mining, machine learning, and biological population division, etc. Moreover, robust variant for [Formula: see text]-means problem, which includes [Formula: see text]-means with penalties and [Formula: see text]-means with outliers, is also an active research branch. Most of these problems are NP-hard even the most classical problem, [Formula: see text]-means problem. For the NP-hard problems, the heuristic algorithm is a powerful method. When the quality of the output can be guaranteed, the algorithm is called an approximation algorithm. <\/jats:p><jats:p> In this paper, combining two types of robust settings, we consider [Formula: see text]-means problem with penalties and outliers ([Formula: see text]-MPO). In the [Formula: see text]-MPO, we are given an [Formula: see text]-point set [Formula: see text], a penalty cost [Formula: see text] for each [Formula: see text], an integer [Formula: see text], and an integer [Formula: see text]. The target is to find a center subset [Formula: see text] with [Formula: see text], a penalty subset [Formula: see text] and an outlier subset [Formula: see text] with [Formula: see text], such that the sum of the total costs, including the connection cost and the penalty cost, is minimized. We offer an approximation algorithm using a heuristic local search scheme. Based on a single-swap manipulation, we obtain [Formula: see text]-approximation algorithm. <\/jats:p>","DOI":"10.1142\/s0217595922400097","type":"journal-article","created":{"date-parts":[[2022,2,8]],"date-time":"2022-02-08T04:42:15Z","timestamp":1644295335000},"source":"Crossref","is-referenced-by-count":0,"title":["Effective Heuristic Techniques for Combined Robust Clustering Problem"],"prefix":"10.1142","volume":"40","author":[{"given":"Yunhe","family":"Xu","sequence":"first","affiliation":[{"name":"Institute of Operations Research and Systems Engineering, College of Science, Tianjin University of Technology, No. 391 Binshui Xi Road, Tianjin 300384, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chenchen","family":"Wu","sequence":"additional","affiliation":[{"name":"Institute of Operations Research and Systems Engineering, College of Science, Tianjin University of Technology, No. 391 Binshui Xi Road, Tianjin 300384, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ling","family":"Gai","sequence":"additional","affiliation":[{"name":"Glorious Sun School of Business & Management, Donghua University, Shanghai 200051, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lu","family":"Han","sequence":"additional","affiliation":[{"name":"School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2022,2,7]]},"reference":[{"key":"S0217595922400097BIB001","first-page":"61","volume-title":"Proc. FOCS","author":"Ahmadian S","year":"2017"},{"key":"S0217595922400097BIB002","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s10994-009-5103-0","volume":"75","author":"Aloise D","year":"2009","journal-title":"Machine Learning"},{"key":"S0217595922400097BIB003","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1137\/S0097539702416402","volume":"33","author":"Arya V","year":"2004","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"S0217595922400097BIB004","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/2981561","volume":"13","author":"Byrka J","year":"2017","journal-title":"ACM Transactions on Algorithms"},{"key":"S0217595922400097BIB005","first-page":"642","volume-title":"Proc. SODA","author":"Charikar M","year":"2001"},{"key":"S0217595922400097BIB006","first-page":"378","volume-title":"Proc. FOCS","author":"Charikar M","year":"1999"},{"key":"S0217595922400097BIB007","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1006\/jcss.2002.1882","volume":"65","author":"Charikar M","year":"2002","journal-title":"Journal of Computer and System Sciences"},{"key":"S0217595922400097BIB008","first-page":"329","volume-title":"Proc. SoCG","author":"Cohen-Addad V","year":"2015"},{"key":"S0217595922400097BIB009","first-page":"353","volume-title":"Proc. FOCS","author":"Cohen-Addad V","year":"2016"},{"key":"S0217595922400097BIB010","first-page":"49","volume-title":"Proc. FOCS","author":"Cohen-Addad V","year":"2017"},{"key":"S0217595922400097BIB012","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1023\/A:1007612920971","volume":"42","author":"Dhillon IS","year":"2001","journal-title":"Machine Learning"},{"key":"S0217595922400097BIB013","first-page":"365","volume-title":"Proc. FOCS","author":"Friggstad Z","year":"2016"},{"key":"S0217595922400097BIB014","first-page":"75:1","volume-title":"Proc. ICALP","author":"Friggstad Z","year":"2016"},{"key":"S0217595922400097BIB015","first-page":"398","volume-title":"Proc. SODA","author":"Friggstad Z","year":"2018"},{"key":"S0217595922400097BIB016","first-page":"61:1","volume-title":"Proc. ISAAC","author":"Feng Q","year":"2019"},{"key":"S0217595922400097BIB017","first-page":"170","volume-title":"Proc. FAW","author":"Feng Q","year":"2019"},{"key":"S0217595922400097BIB018","first-page":"757","volume-title":"Proc. VLDB Endowment","author":"Gupta S","year":"2017"},{"issue":"10","key":"S0217595922400097BIB019","doi-asserted-by":"crossref","first-page":"1","DOI":"10.18637\/jss.v050.i10","volume":"50","author":"Hornik K","year":"2012","journal-title":"Journal of Statistical Software"},{"key":"S0217595922400097BIB020","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"Jain K","year":"2001","journal-title":"Journal of the ACM"},{"key":"S0217595922400097BIB021","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/j.comgeo.2004.03.003","volume":"28","author":"Kanungo T","year":"2004","journal-title":"Computational Geometry: Theory and Applications"},{"key":"S0217595922400097BIB023","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"Lloyd S","year":"1982","journal-title":"IEEE Transactions on Information Theory"},{"issue":"1","key":"S0217595922400097BIB024","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/s10878-019-00450-w","volume":"39","author":"Li M","year":"2020","journal-title":"Journal of Combinatorial Optimization"},{"key":"S0217595922400097BIB025","first-page":"274","volume-title":"Proc. WALCOM","author":"Mahajan M","year":"2009"},{"key":"S0217595922400097BIB026","first-page":"14:1","volume-title":"Proc. APPROX\/RONDOM","author":"Makarychev K","year":"2016"},{"key":"S0217595922400097BIB027","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/s004540010019","volume":"24","author":"Matous\u0306ek J","year":"2000","journal-title":"Discrete & Computational Geometry"},{"key":"S0217595922400097BIB028","first-page":"646","volume-title":"Proc. ACM STOC","author":"Ravishankar K","year":"2018"},{"issue":"3","key":"S0217595922400097BIB029","doi-asserted-by":"crossref","first-page":"709","DOI":"10.1007\/s11081-020-09503-0","volume":"21","author":"Xu Y","year":"2019","journal-title":"Optimization and Engineering"},{"issue":"1","key":"S0217595922400097BIB030","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/s10898-015-0394-0","volume":"67","author":"Xu Y","year":"2017","journal-title":"Journal of Global Optimization"},{"key":"S0217595922400097BIB031","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/j.tcs.2017.03.014","volume":"774","author":"Xu Y","year":"2019","journal-title":"Theoretical Computer Science"},{"key":"S0217595922400097BIB032","first-page":"568","volume-title":"Proc. COCOON","author":"Zhang D","year":"2017"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595922400097","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,16]],"date-time":"2023-03-16T05:53:41Z","timestamp":1678946021000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0217595922400097"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,7]]},"references-count":30,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["10.1142\/S0217595922400097"],"URL":"https:\/\/doi.org\/10.1142\/s0217595922400097","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"type":"print","value":"0217-5959"},{"type":"electronic","value":"1793-7019"}],"subject":[],"published":{"date-parts":[[2022,2,7]]},"article-number":"2240009"}}