2 papers
cs.DS2022
Improved Bi-point Rounding Algorithms and a Golden Barrier for -Median
Kishen N. Gowda, Thomas Pensyl, Aravind Srinivasan +1
The current best approximation algorithms for -median rely on first obtaining a structured fractional solution known as a bi-point solution, and then rounding it to an integer s…
cs.DS2017
A Lottery Model for Center-type Problems With Outliers
David G. Harris, Thomas Pensyl, Aravind Srinivasan +1
In this paper, we give tight approximation algorithms for the -center and matroid center problems with outliers. Unfairness arises naturally in this setting: certain clients cou…