In　this　paper,　we　study　the　k-means　problem　with　(nonuniform)　penalties　(k-MPWP)　which　is　a　natural　generalization　of　the　classic　k-means　problem.　In　the　k-MPWP,　we　are　given　an　n-client　set　mathcal　{D}subsetmathbb　{R}^d,　a　penalty　cost　p:j＞0　for　each　jinmathcal　{D},　and　an　integer　kle　n.　The　goal　is　to　open　a　center　subset　Fsubsetmathbb　{R}^d　with　|F|le　k　and　to　choose　a　client　subset　Psubseteqmathcal　{D}　as　the　penalized　client　set　such　that　the　total　cost　(including　the　sum　of　squares　of　distance　for　each　client　in　mathcal　{D}setminus　P　to　the　nearest　open　center　and　the　sum　of　penalty　cost　for　each　client　in　P)　is　minimized.　We　offer　a　local　search　(81+varepsilon)　-approximation　algorithm　for　the　k-MPWP　by　using　single-swap　operation.　We　further　improve　the　above　approximation　ratio　to　(25+varepsilon)　by　using　multi-swap　operation.　©　2017,　Springer　International　Publishing　AG.