# $k$ -center with outliers - but the points are on a line

The classic $k$-center with outliers problem is NP-hard and there exist approximation algorithms to solve it.

However, what if we assume that the input point are on a line, rather than in an arbitrary metric space?

Does the problem become polytime solvable? Can someone link me to reading on this topic?

• Can you give a self-contained definition of the "classic k-center with outliers" problem? I know what the k-center problem is, but I'm not sure how the "with outliers" part changes the problem definition. In any case, have you tried sorting the points and applying dynamic programming?
– D.W.
Aug 7 '18 at 17:05
• Cross-posted: cs.stackexchange.com/q/96052/755, cstheory.stackexchange.com/q/41332/5038. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted.
– D.W.
Aug 8 '18 at 1:22