We　present　a　(1　+　√3　+　Ε)-approximation　algorithm　for　the　k-median　problem　with　uniform　penalties　in　polynomial　time,　extending　the　recent　result　by　Li　and　Svensson　for　the　classical　k-median　problem　without　penalties.　One　important　difference　of　this　work　from　that　of　Li　and　Svensson　is　a　new　definition　of　sparse　instance　to　exploit　the　combinatorial　structure　of　our　problem.　©　Springer　International　Publishing　AG　2016.