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　D　subset　of　R-d,　a　penalty　cost　p　(j)　＞　0　for　each　j.　D,　and　an　integer　k　＜=　n.　The　goal　is　to　open　a　center　subset　F　subset　of　R-d　with　vertical　bar　F　vertical　bar　＜=　k　and　to　choose　a　client　subset　P　subset　of　D　as　the　penalized　client　set　such　that　the　total　cost　(including　the　sum　of　squares　of　distance　for　each　client　in　D\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　+　epsilon)-approximation　algorithm　for　the　k-MPWP　by　using　single-swap　operation.　We　further　improve　the　above　approximation　ratio　to　(25　+　epsilon)　by　using　multi-swap　operation.