# A Lottery Model for Center-type Problems With Outliers

arXiv: https://arxiv.org/abs/1710.00287 · HTML: https://mlsanity.com/paper/1710.00287/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Oct 2017.

## Built on by (most cited first, 8 of 8)

- [Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints](https://mlsanity.com/paper/2103.02013/) (2021)
- [How to Find a Good Explanation for Clustering?](https://mlsanity.com/paper/2112.06580/) (2021)
- [Efficient Algorithms For Fair Clustering with a New Fairness Notion](https://mlsanity.com/paper/2109.00708/) (2021)
- [Revisiting Priority k-Center: Fairness and Outliers](https://mlsanity.com/paper/2103.03337/) (2021)
- [Fair Disaster Containment via Graph-Cut Problems](https://mlsanity.com/paper/2106.05424/) (2021)
- [Fair Clustering: Critique, Caveats, and Future Directions](https://mlsanity.com/paper/2406.15960/) (2024)
- [k-Center Clustering with Outliers in Sliding Windows](https://mlsanity.com/paper/2201.02448/) (2022)
- [Individual Fairness under Varied Notions of Group Fairness in Bipartite Matching - One Framework to Approximate Them All](https://mlsanity.com/paper/2208.09951/) (2022)

## Abstract (arXiv)

In this paper, we give tight approximation algorithms for the k-center and matroid center problems with outliers. Unfairness arises naturally in this setting: certain clients could always be considered as outliers. To address this issue, we introduce a lottery model in which each client j is allowed to submit a parameter pj ∈ [0,1] and we look for a random solution that covers every client j with probability at least pj. Our techniques include a randomized rounding procedure to round a point inside a matroid intersection polytope to a basis plus at most one extra item such that all marginal probabilities are preserved and such that a certain linear function of the variables does not decrease in the process with probability one.