We　present　a　(1　+　root　3　+　is　an　element　of)-approximation　algorithm　for　the　k-median　problem　with　uniform　penalties,　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.　(C)　2018　Elsevier　B.V.　All　rights　reserved.