License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.69
URN: urn:nbn:de:0030-drops-62153
URL: http://drops.dagstuhl.de/opus/volltexte/2016/6215/
Go to the corresponding LIPIcs Volume Portal


Ahmadian, Sara ; Swamy, Chaitanya

Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers

pdf-format:
LIPIcs-ICALP-2016-69.pdf (0.7 MB)


Abstract

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.

BibTeX - Entry

@InProceedings{ahmadian_et_al:LIPIcs:2016:6215,
  author =	{Sara Ahmadian and Chaitanya Swamy},
  title =	{{Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{69:1--69:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6215},
  URN =		{urn:nbn:de:0030-drops-62153},
  doi =		{10.4230/LIPIcs.ICALP.2016.69},
  annote =	{Keywords: Approximation algorithms, facililty-location problems, primal-dual method, Lagrangian relaxation, k-center problems, minimizing sum of radii}
}

Keywords: Approximation algorithms, facililty-location problems, primal-dual method, Lagrangian relaxation, k-center problems, minimizing sum of radii
Seminar: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue Date: 2016
Date of publication: 17.08.2016


DROPS-Home | Imprint | Privacy Published by LZI