We study the $mathcal{F}$-center problem with outliers: given a metric space $(X,d)$, a general down-closed family $mathcal{F}$ of subsets of $X$, and a parameter $m$, we need to locate a subset $Sin mathcal{F}$ of centers such that the maximum distance among the closest $m$ points in $X$ to $S$ is minimized. Our main result is a dichotomy theorem. Colloquially, we prove that there is an efficient $3$-approximation for the $mathcal{F}$-center problem with outliers if and only if we can efficiently optimize a poly-bounded linear function over $mathcal{F}$ subject to a partition constraint. One concrete upshot of our result is a polynomial time $3$-approximation for the knapsack center problem with outliers for which no (true) approximation algorithm was known.
Download