{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,29]],"date-time":"2023-08-29T09:09:58Z","timestamp":1693300198785},"reference-count":21,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2020,8]]},"abstract":"<jats:p> As a classic NP-hard problem in machine learning and computational geometry, the [Formula: see text]-means problem aims to partition a data point set into [Formula: see text] clusters such that the sum of the squared distance from each point to its nearest center is minimized. The [Formula: see text]-means problem with penalties, denoted by [Formula: see text]-MPWP, generalizing the [Formula: see text]-means problem, allows that some points can be paid some penalties instead of being clustered. In this paper, we study the seeding algorithm of [Formula: see text]-MPWP and propose a parallel seeding algorithm for [Formula: see text]-MPWP along with the corresponding theoretical analysis. <\/jats:p>","DOI":"10.1142\/s0217595920400059","type":"journal-article","created":{"date-parts":[[2020,5,19]],"date-time":"2020-05-19T05:37:52Z","timestamp":1589866672000},"page":"2040005","source":"Crossref","is-referenced-by-count":1,"title":["The Parallel Seeding Algorithm for k-Means Problem with Penalties"],"prefix":"10.1142","volume":"37","author":[{"given":"Min","family":"Li","sequence":"first","affiliation":[{"name":"School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[{"name":"Department of Operations Research and Scientific Computing, Beijing University of Technology, Beijing 100124, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun","family":"Yue","sequence":"additional","affiliation":[{"name":"School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dongmei","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Shandong Jianzhu University, Jinan 250101, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2020,5,19]]},"reference":[{"key":"S0217595920400059BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_2"},{"key":"S0217595920400059BIB002","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.15"},{"key":"S0217595920400059BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-009-5103-0"},{"key":"S0217595920400059BIB004","first-page":"1027","volume-title":"Proceedings of SODA","author":"Arthur D","year":"2007"},{"key":"S0217595920400059BIB005","first-page":"55","volume-title":"Proceedings of NIPS","author":"Bachem O","year":"2016"},{"key":"S0217595920400059BIB006","first-page":"292","volume-title":"Proceedings of ICML","author":"Bachem O","year":"2017"},{"key":"S0217595920400059BIB007","doi-asserted-by":"publisher","DOI":"10.14778\/2180912.2180915"},{"key":"S0217595920400059BIB008","doi-asserted-by":"crossref","unstructured":"Bl\u00f6mer, J,  C Lammersen,  M Schmidt and  C Sohler  (2016).  Theoretical analysis of the k-means algorithm \u2014 A survey. Algorithm Engineering,  Springer International Publishing, 2016,  pp. 81\u2013116.","DOI":"10.1007\/978-3-319-49487-6_3"},{"key":"S0217595920400059BIB010","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033113.59016.96"},{"key":"S0217595920400059BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-18126-0_15"},{"key":"S0217595920400059BIB012","doi-asserted-by":"publisher","DOI":"10.1126\/science.1136800"},{"key":"S0217595920400059BIB013","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375845"},{"key":"S0217595920400059BIB014","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.003"},{"key":"S0217595920400059BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-019-00450-w"},{"key":"S0217595920400059BIB016","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-019-00779-w"},{"key":"S0217595920400059BIB017","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"S0217595920400059BIB018","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395117"},{"key":"S0217595920400059BIB019","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btm320"},{"key":"S0217595920400059BIB020","first-page":"101","volume":"21","author":"Xu D","year":"2017","journal-title":"Operations Research Transactions"},{"key":"S0217595920400059BIB021","first-page":"31","volume":"22","author":"Xu D","year":"2018","journal-title":"Operations Research Transactions"},{"key":"S0217595920400059BIB022","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-018-0278-6"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595920400059","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,28]],"date-time":"2020-08-28T08:33:07Z","timestamp":1598603587000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0217595920400059"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,19]]},"references-count":21,"journal-issue":{"issue":"04","published-print":{"date-parts":[[2020,8]]}},"alternative-id":["10.1142\/S0217595920400059"],"URL":"https:\/\/doi.org\/10.1142\/s0217595920400059","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"value":"0217-5959","type":"print"},{"value":"1793-7019","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,19]]}}}