k-Median/Means with Outliers Revisited: A Simple Fpt Approximation

We revisit the classical metric k-median/means with outliers in this paper, whose proposal dates back to (Charikar, Khuller, Mount, and Narasimhan SODA’01). Though good approximation algorithms have been proposed, referring to the state-of-the-art (6.994+ \(\varepsilon \) )-approximation (Gupta, Moseley and Zhou ICALP’21) for k-median with outliers and (53.002+ \(\varepsilon \) )-approximation (Krishnaswamy, Li, and Sandeep SODA’18) for k-means with outliers respectively, we are interested in finding efficient fpt (fixed-parameter tractable) approximations, following a recent research mainstream for constrained clusterings. As our main contribution, we propose a simple but efficient technical framework that yields a \((3+\varepsilon )\) / \((9+\varepsilon )\) -approximation for k-median/means with outliers, albeit in \(((m +k)/\varepsilon )^{O(k)} \cdot n^{O(1)}\) time. It is notable that our results match with previous result (Goyal, Jaiswal, and Kumar IPEC’20) in terms of ratio and asymptotic running time. But as aforementioned, our technique is much more simplified and straightforward, where instead of considering the whole client set, we restrict ourselves to finding a good approximate facility set for coreset, which can be done easily in fpt time even with provably small loss. Similar idea can be applied to more constrained clustering problems whose coresets have been well-studied.