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　is　an　element　of　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.