We　study　a　problem　called　the　k-means　problem　with　penalties　(k-MPWP),　which　is　a　natural　generalization　of　the　typical　k-means　problem.　In　this　problem,　we　have　a　set　D　of　client　points　in　Rd,　a　set　F　of　possible　centers　in　Rd,　and　a　penalty　cost　pj＞0　for　each　point　j∈D.　We　are　also　given　an　integer　k　which　is　the　size　of　the　center　point　set.　We　want　to　find　a　center　point　set　S⊆F　with　size　k,　choose　a　penalized　subset　of　clients　P⊆D,　and　assign　every　client　in　D\P　to　its　open　center.　Our　goal　is　to　minimize　the　sum　of　the　squared　distances　between　every　point　in　D\P　to　its　assigned　centre　point　and　the　sum　of　the　penalty　costs　for　all　clients　in　P.　By　using　the　multi-swap　local　search　technique　and　under　the　fixed-dimensional　Euclidean　space　setting,　we　present　a　polynomial-time　approximation　scheme　(PTAS)　for　the　k-MPWP.　©　Operations　Research　Society　of　China,　Periodicals　Agency　of　Shanghai　University,　Science　Press,　and　Springer-Verlag　GmbH　Germany,　part　of　Springer　Nature　2022.