Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers

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.