We　present　two　local　search　algorithms　for　the　k-median　and　k-facility　location　problems　with　linear　penalties　(k-MLP　and　k-FLPLP),　two　extensions　of　the　classical　k-median　and　k-facility　location　problems　respectively.　We　show　that　the　approximation　ratios　of　these　two　algorithms　are　3　+　2/p　+　epsilon　for　the　k-MLP,　and　2　+　1/p　+　root　3　+　2/p　+　1/p(2)　+　epsilon　for　the　k-FLPLP,　respectively,　where　p　is　an　element　of　Z(+)　is　a　parameter　of　the　algorithms　and　epsilon　＞　0　is　a　positive　number.　In　particular,　the　(3　+　2/p　+　epsilon)-approximation　improves　the　best　known　4-approximation　for　the　k-MLP　for　any　p　＞　2.