47 citations · 57 across the 9 of their papers we have counts for
6 papers · 1 filter
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…
Approximation algorithms for stochastic clustering
David G. Harris, Shi Li, Thomas Pensyl +2
We consider stochastic settings for clustering, and develop provably-good approximation algorithms for a number of these notions. These algorithms yield better approximation ratios…
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…
Dependent randomized rounding for clustering and partition systems with knapsack constraints
David G. Harris, Thomas Pensyl, Aravind Srinivasan +1
Clustering problems are fundamental to unsupervised learning. There is an increased emphasis on fairness in machine learning and AI; one representative notion of fairness is that n…
Fairness in Resource Allocation and Slowed-down Dependent Rounding
David G. Harris, Thomas Pensyl, Aravind Srinivasan +1
We consider an issue of much current concern: could fairness, an issue that is already difficult to guarantee, worsen when algorithms run much of our lives? We consider this in the…
An Improved Approximation for -median, and Positive Correlation in Budgeted Optimization
Jarosław Byrka, Thomas Pensyl, Bartosz Rybicki +2
Dependent rounding is a useful technique for optimization problems with hard budget constraints. This framework naturally leads to \emph{negative correlation} properties. However,…