# Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Aug 2016.

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

- [Tight FPT Approximation for Constrained k-Center and k-Supplier](https://mlsanity.com/paper/2110.14242/) (2021)
- [Coresets for constrained k-median and k-means clustering in low dimensional Euclidean space](https://mlsanity.com/paper/2106.07319/) (2021)
- [Clustering to Minimize Cluster-Aware Norm Objectives](https://mlsanity.com/paper/2410.24104/) (2024)
- [Distribution free optimality intervals for clustering](https://mlsanity.com/paper/2107.14442/) (2021)
- [Approximating Fair k-Min-Sum-Radii in Euclidean Space](https://mlsanity.com/paper/2309.00834/) (2023)
- [A Broader View on Clustering under Cluster-Aware Norm Objectives](https://mlsanity.com/paper/2512.06211/) (2025)

## Abstract (arXiv)

We consider clustering problems with em non-uniform lower bounds and outliers, and obtain the em first approximation guarantees for these problems. We have a set F of facilities with lower bounds Lii∈F and a set D of clients located in a common metric space c(i,j)i,j∈FcupD, and bounds k, m. A feasible solution is a pair bigl(SsseF,σ:Dmapsto Scupmathsfoutbigr), where σ specifies the client assignments, such that |S|≤ k, |σ-1(i)|≥ Li for all i∈ S, and |σ-1(mathsfout)|≤ m. In the em lower-bounded min-sum-of-radii with outliers (lbksro) problem, the objective is to minimize sumi∈ Smax_j∈σ-1(i)c(i,j), and in the em lower-bounded k-supplier with outliers (lbkso) problem, the objective is to minimize maxi∈ Smax_j∈σ-1(i)c(i,j). We obtain an approximation factor of 12.365 for lbksro, which improves to 3.83 for the non-outlier version (i.e., m=0). These also constitute the em first approximation bounds for the min-sum-of-radii objective when we consider lower bounds and outliers em separately. We apply the primal-dual method to the relaxation where we Lagrangify the |S|≤ k constraint. The chief technical contribution and novelty of our algorithm is that, departing from the standard paradigm used for such constrained problems, we obtain an O(1)-approximation em despite the fact that we do not obtain a Lagrangian-multiplier-preserving algorithm for the Lagrangian relaxation. We believe that our ideas have broader applicability to other clustering problems with outliers as well. We obtain approximation factors of 5 and 3 respectively for lbkso and its non-outlier version. These are the em first approximation results for k-supplier with em non-uniform lower bounds.