In　the　classical　k-means　problem,　we　are　given　a　data　set　and　an　integer　k.　The　object　is　to　select　a　set　of　size　at　most　k　such　that　each　point　in　is　connected　to　the　closet　cluster　in　S　with　minimum　total　squared　distances.　However,　in　some　real-life　applications,　it　is　more　desirable　and　beneficial　to　pay　a　small　penalty　for　not　connecting　some　outliers　in　that　are　too　far　away　from　most　points.　As　a　result,　we　are　motivated　to　study　the　k-means　problem　with　penalties,　for　which　we　propose　a　-approximation　algorithm　via　the　primal-dual　technique,　improving　the　previous　best　approximation　ratio　of　in[7]　also　by　using　the　primal-dual　technique.　©　2020,　Springer　Nature　Switzerland　AG.