A More Efficient Reduction from Outlier-Aware to Outlier-Free k-Median

Given a non-negative integer $\ell$, the $k$-median with outliers problem extends the standard $k$-median problem by allowing the removal of up to $\ell$ points and minimizing the clustering cost over the remaining ones. Algorithmic development in this setting remains an active area of research due to its relevance in processing noisy data. In this paper, we present a sampling-based reduction from the $k$-median with outliers problem to its outlier-free counterpart. The reduction incurs a multiplicative overhead of $(k\ell^{-1} + \varepsilon^{-1})^{O(\ell)}$ in the running time and an arbitrarily small loss in the approximation ratio. This improves upon previously known reductions with overheads of $((k + \ell)\varepsilon^{-1})^{O(\ell)}n^{O(1)}$ and $((k + \ell)\varepsilon^{-1})^{O(\ell)}$, given by Agrawal et al. (AAAI 2023) and Jaiswal and Kumar (ISAAC 2023), respectively. As applications, we obtain faster fixed-parameter tractable (FPT) algorithms with tight approximation guarantees for the $k$-median with outliers problem under various metric spaces. Furthermore, our approach naturally generalizes to constrained variants of the problem where additional constraints are imposed on the cluster sizes, and yields similar improvements in their FPT approximations.