As　a　classic　NP-hard　problem　in　machine　learning　and　computational　geometry,　the　k-means　problem　aims　to　partition　the　given　points　into　k　sets　to　minimize　the　within-cluster　sum　of　squares.　The　k-means　problem　with　penalties　(k-MPWP),　as　a　generalizing　problem　of　the　k-means　problem,　allows　a　point　that　can　be　either　clustered　or　penalized　with　some　positive　cost.　In　this　paper,　we　mainly　apply　the　parallel　seeding　algorithm　to　the　k-MPWP,　and　show　sufficient　analysis　to　bound　the　expected　solution　quality　in　the　case　where　both　the　number　of　iterations　and　the　number　of　points　sampled　in　each　iteration　can　be　given　arbitrarily.　The　approximate　guarantee　can　be　obtained　as　O(f(M)lnk),　where　f(M)　is　a　polynomial　function　involving　the　maximal　ratio　M　between　the　penalties.　On　one　hand,　this　result　can　be　viewed　as　a　further　improvement　on　the　parallel　algorithm　for　k-MPWP　given　by　Li　et　al.,　where　the　number　of　iterations　depends　on　other　factors.　On　the　other　hand,　our　result　also　generalizes　the　one　solving　the　k-means　problem　presented　by　Bachem　et　al.,　because　k-MPWP　is　a　variant　of　the　k-means　problem.　Moreover,　we　present　a　numerical　experiment　to　show　the　effectiveness　of　the　parallel　algorithm　for　k-means　with　penalties.