In　this　paper,　we　explore　two　robust　models　for　the　k-median　and　k-means　problems:　the　outlier-version　(k-MedO/k-MeaO)　and　the　penalty-version　(k-MedP/k-MeaP),　enabling　the　marking　and　elimination　of　certain　points　as　outliers.　In　k-MedO/k-MeaO,　the　count　of　outliers　is　restricted　by　a　specified　integer,　while　in　k-MedP/k-MeaP,　there’s　no　explicit　limit　on　outlier　quantity,　yet　each　outlier　incurs　a　penalty　cost.　We　introduce　a　novel　approach　to　evaluate　the　approximation　ratio　of　local　search　algorithms　for　these　problems.　This　involves　an　adapted　clustering　method　that　captures　pertinent　information　about　outliers　within　both　local　and　global　optimal　solutions.　For　k-MeaP,　we　enhance　the　best-known　approximation　ratio　derived　from　local　search,　elevating　it　from　25+ε　to　9+ε.　The　best-known　approximation　ratio　for　k-MedP　is　also　obtained.　Regarding　k-MedO/k-MeaO,　only　two　bi-criteria　approximation　algorithms　based　on　local　search　exist.　One　violates　the　outlier　constraint　(limiting　outlier　count),　while　the　other　breaches　the　cardinality　constraint　(restricting　the　number　of　clusters).　We　focus　on　the　former　algorithm,　enhancing　its　approximation　ratios　from　17+ε　to　3+ε　for　k-MedO　and　from　274+ε　to　9+ε　for　k-MeaO.　©　The　Author(s),　under　exclusive　license　to　Springer　Nature　Singapore　Pte　Ltd.　2024.