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　R-d,　a　set　F　of　possible　centers　in　R-d,　and　a　penalty　cost　p(j)　＞　0　for　each　point　j　is　an　element　of　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　subset　of　F　with　size　k,　choose　a　penalized　subset　of　clients　P　subset　of　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.