REU Project
- 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) | Jelena Glisic | Charles University (Prague, Czech Republic) | Patrik Zavoral | Charles University (Prague, Czech Republic)
- Project Mentor (s) : Karthik Srikanta - 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.