2026-07-23T17:34:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6215 2024-03-06T10:37:46Z ddc:004 open_access

Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers Ahmadian, Sara Swamy, Chaitanya Approximation algorithms facililty-location problems primal-dual method Lagrangian relaxation k-center problems minimizing sum of radii We consider clustering problems with non-uniform lower bounds and outliers, and obtain the first approximation guarantees for these problems. We have a set F of facilities with lower bounds {L_i}_{i in F} and a set D of clients located in a common metric space {c(i,j)}_{i,j in F union D}, and bounds k, m. A feasible solution is a pair (S subseteq F, sigma: D -> S union {out}), where sigma specifies the client assignments, such that |S| <=k, |sigma^{-1}(i)| >= L_i for all i in S, and |sigma^{-1}(out)| <= m. In the lower-bounded min-sum-of-radii with outliers P (LBkSRO) problem, the objective is to minimize sum_{i in S} max_{j in sigma^{-1})i)}, and in the lower-bounded k-supplier with outliers (LBkSupO) problem, the objective is to minimize max_{i in S} max_{j in sigma^{-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 first approximation bounds for the min-sum-of-radii objective when we consider lower bounds and outliers 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 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 LBkSupO and its non-outlier version. These are the first approximation results for k-supplier with non-uniform lower bounds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sara Ahmadian and Chaitanya Swamy 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.69 urn:nbn:de:0030-drops-62153 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.69 eng https://creativecommons.org/licenses/by/3.0/legalcode