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?

$\endgroup$

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.