- On Approximating Diameter with Outliers
- Project Year:
2024
- REU Student (s):
Todor Antic | Charles University (Prague, Czech Republic)
| Guillermo Gamboa | Charles University (Prague, Czech Republic)
- Student 1 Institution:
Charles University (Prague, Czech Republic)
- Student 2 Institution:
Charles University (Prague, Czech Republic)
- Project Mentor:
Karthik Srikanta
- Project Mentor Area:
Computer Science
- Project Abstract:
We study the furthest pair with outliers problem, where the goal is to identify a given number of outlier points such that the diameter of the remaining pointset is minimized. This is closely related to various clustering problems such as the Max-k-diameter with outliers. We show that the furthest pair with outliers is NP-complete by a reduction from the independent set. Further, we share found limits of (in)approximability for the furthest pair with outliers for the usual ell-p metrics. We report that 4 + ε approximation is efficiently computable and that no PTAS exists for the problem.
