1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$
    – D.W. ♦
    Aug 7 '18 at 17:05
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Aug 8 '18 at 1:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.