Author name cluster

Thomas Pensyl

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

JMLR Journal 2022 Journal Article

Dependent randomized rounding for clustering and partition systems with knapsack constraints

David G. Harris
Thomas Pensyl
Aravind Srinivasan
Khoa Trinh

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 no single group should be over-represented among the cluster-centers. This, and much more general clustering problems, can be formulated with “knapsack" and “partition" constraints. We develop new randomized algorithms targeting such problems, and study two in particular: multi-knapsack median and multi-knapsack center. Our rounding algorithms give new approximation and pseudo-approximation algorithms for these problems. One key technical tool, which may be of independent interest, is a new tail bound analogous to Feige (2006) for sums of random variables with unbounded variances. Such bounds can be useful in inferring properties of large networks using few samples. [abs] [ pdf ][ bib ] &copy JMLR 2022. ( edit, beta )

PDF Details

JMLR Journal 2019 Journal Article

Approximation Algorithms for Stochastic Clustering

David G. Harris
Shi Li
Thomas Pensyl
Aravind Srinivasan
Khoa Trinh

We consider stochastic settings for clustering, and develop provably-good approximation algorithms for a number of these notions. These algorithms yield better approximation ratios compared to the usual deterministic clustering setting. Additionally, they offer a number of advantages including clustering which is fairer and has better long-term behavior for each user. In particular, they ensure that every user is guaranteed to get good service (on average). We also complement some of these with impossibility results. [abs] [ pdf ][ bib ] &copy JMLR 2019. ( edit, beta )

PDF Details

NeurIPS Conference 2018 Conference Paper

Approximation algorithms for stochastic clustering

David Harris
Shi Li
Aravind Srinivasan
Khoa Trinh
Thomas Pensyl

We consider stochastic settings for clustering, and develop provably-good (approximation) algorithms for a number of these notions. These algorithms allow one to obtain better approximation ratios compared to the usual deterministic clustering setting. Additionally, they offer a number of advantages including providing fairer clustering and clustering which has better long-term behavior for each user. In particular, they ensure that every user is guaranteed to get good service (on average). We also complement some of these with impossibility results.

PDF Details