In　the　classical　k-means　problem,　we　are　given　a　data　set　D　subset　of　R-l　and　an　integer　k.　The　object　is　to　select　a　set　S　subset　of　R-l　of　size　at　most　k　such　that　each　point　in　D　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　D　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　(6.357+epsilon)-approximation　algorithm　via　the　primal-dual　technique,　improving　the　previous　best　approximation　ratio　of　19.849　+　is　an　element　of　in　[7]　also　by　using　the　primal-dual　technique.