As　a　classic　NP-hard　problem　in　machine　learning　and　computational　geometry,　the　k-means　problem　aims　to　partition　a　data　point　set　into　k　clusters　such　that　the　sum　of　the　squared　distance　from　each　point　to　its　nearest　center　is　minimized.　The　k-means　problem　with　penalties,　denoted　by　k-MPWP,　generalizing　the　k-means　problem,　allows　that　some　points　can　be　paid　some　penalties　instead　of　being　clustered.　In　this　paper,　we　study　the　seeding　algorithm　of　k-MPWP　and　propose　a　parallel　seeding　algorithm　for　k-MPWP　along　with　the　corresponding　theoretical　analysis.