{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T21:57:16Z","timestamp":1747173436208,"version":"3.40.5"},"reference-count":20,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2021,8,16]],"date-time":"2021-08-16T00:00:00Z","timestamp":1629072000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In the <jats:italic>k<\/jats:italic>-means problem with penalties, we are given a data set <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129521000104_inline1.png\"\/><jats:tex-math>$${\\cal D} \\subseteq \\mathbb{R}^\\ell $$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of <jats:italic>n<\/jats:italic> points where each point <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129521000104_inline2.png\"\/><jats:tex-math>$$j \\in {\\cal D}$$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is associated with a penalty cost <jats:italic>p<\/jats:italic><jats:sub><jats:italic>j<\/jats:italic><\/jats:sub> and an integer <jats:italic>k<\/jats:italic>. The goal is to choose a set <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129521000104_inline3.png\"\/><jats:tex-math>$${\\rm{C}}S \\subseteq {{\\cal R}^\\ell }$$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> with |CS| \u2264 <jats:italic>k<\/jats:italic> and a penalized subset <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129521000104_inline4.png\"\/><jats:tex-math>$${{\\cal D}_p} \\subseteq {\\cal D}$$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> to minimize the sum of the total squared distance from the points in <jats:italic>D \/ D<\/jats:italic><jats:sub><jats:italic>p<\/jats:italic><\/jats:sub> to CS and the total penalty cost of points in <jats:italic>D<\/jats:italic><jats:sub><jats:italic>p<\/jats:italic><\/jats:sub>, namely <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129521000104_inline5.png\"\/><jats:tex-math>$$\\sum\\nolimits_{j \\in {\\cal D}\\backslash {{\\cal D}_p}}  {d^2}(j,{\\rm{C}}S) + \\sum\\nolimits_{j \\in {{\\cal D}_p}}  {p_j}$$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We employ the primal-dual technique to give a pseudo-polynomial time algorithm with an approximation ratio of (6.357+<jats:italic>\u03b5<\/jats:italic>) for the <jats:italic>k<\/jats:italic>-means problem with penalties, improving the previous best approximation ratio 19.849+<jats:italic>\u220a<\/jats:italic> for this problem given by Feng et al. in Proceedings of FAW (2019).<\/jats:p>","DOI":"10.1017\/s0960129521000104","type":"journal-article","created":{"date-parts":[[2021,8,16]],"date-time":"2021-08-16T08:54:00Z","timestamp":1629104040000},"page":"151-163","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["An improved primal-dual approximation algorithm for the <i>k<\/i>-means problem with penalties"],"prefix":"10.1017","volume":"32","author":[{"given":"Chunying","family":"Ren","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Donglei","family":"Du","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2784-5073","authenticated-orcid":false,"given":"Min","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2021,8,16]]},"reference":[{"key":"S0960129521000104_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-019-00450-w"},{"key":"S0960129521000104_ref1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.15"},{"key":"S0960129521000104_ref7","doi-asserted-by":"publisher","DOI":"10.1145\/1247069.1247072"},{"key":"S0960129521000104_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-009-5103-0"},{"key":"S0960129521000104_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-020-00569-1"},{"key":"S0960129521000104_ref10","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375845"},{"key":"S0960129521000104_ref9","doi-asserted-by":"publisher","DOI":"10.1137\/17M1127181"},{"key":"S0960129521000104_ref4","unstructured":"Charikar, M. , Khuller, S. , Mount, D. M. and Narasimhan, G. (2001). Algorithms for facility location problems with outliers. In: Proceedings of 12th ACM-SIAM Symposium on Discrete Algorithms, 642\u2013651."},{"key":"S0960129521000104_ref6","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033113.59016.96"},{"key":"S0960129521000104_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.003"},{"key":"S0960129521000104_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-18126-0_15"},{"key":"S0960129521000104_ref5","doi-asserted-by":"publisher","DOI":"10.1137\/17M112717X"},{"key":"S0960129521000104_ref16","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"S0960129521000104_ref3","unstructured":"Arthur, D. and Vassilvitskii, S. (2007). k-means++: the advantages of careful seeding. In: Proceedings of SODA, 1027\u20131035."},{"key":"S0960129521000104_ref17","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316350"},{"volume-title":"Approximation Algorithms","year":"2001","author":"Vazirani","key":"S0960129521000104_ref18"},{"key":"S0960129521000104_ref19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735"},{"key":"S0960129521000104_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-020-00537-9"},{"key":"S0960129521000104_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9911-7"},{"key":"S0960129521000104_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-018-0278-6"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129521000104","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,15]],"date-time":"2022-11-15T10:28:41Z","timestamp":1668508121000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129521000104\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,16]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["S0960129521000104"],"URL":"https:\/\/doi.org\/10.1017\/s0960129521000104","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"type":"print","value":"0960-1295"},{"type":"electronic","value":"1469-8072"}],"subject":[],"published":{"date-parts":[[2021,8,16]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}