Ahmadian, Sara ;
Swamy, Chaitanya
Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers
Abstract
We consider clustering problems with nonuniform 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 lowerbounded minsumofradii with outliers P (LBkSRO) problem, the objective is to minimize sum_{i in S} max_{j in sigma^{1})i)}, and in the lowerbounded ksupplier 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 nonoutlier version (i.e., m = 0). These also constitute the first approximation bounds for the minsumofradii objective when we consider lower bounds and outliers separately. We apply the primaldual 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 Lagrangianmultiplierpreserving 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 nonoutlier version. These are the first approximation results for ksupplier with nonuniform 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:169:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6215},
URN = {urn:nbn:de:0030drops62153},
doi = {10.4230/LIPIcs.ICALP.2016.69},
annote = {Keywords: Approximation algorithms, facililtylocation problems, primaldual method, Lagrangian relaxation, kcenter problems, minimizing sum of radii}
}
23.08.2016
Keywords: 

Approximation algorithms, facililtylocation problems, primaldual method, Lagrangian relaxation, kcenter problems, minimizing sum of radii 
Seminar: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Issue date: 

2016 
Date of publication: 

23.08.2016 