2016/08/04 by Sara Ahmadian, Ahmadian, Sara, Chaitanya Swamy +1 · 1 citation
Business, Management and Accounting · #Facility Location and Emergency Management
paper · pdf · doi:10.48550/arxiv.1608.01700
We consider clustering problems with em non-uniform lower bounds and\noutliers, and obtain the em first approximation guarantees for these\nproblems. We have a set F of facilities with lower bounds Li i\∈ F\nand a set D of clients located in a common metric space\n c(i,j) i,j\∈ F\∪ D, and bounds k, m. A feasible solution is a\npair \(S sse F,\σ: D\↦ S\∪ \out \), where\n\σ specifies the client assignments, such that |S|\≤ k,\n|\σ-1(i)|\≥ Li for all i\∈ S, and\n|\σ-1(\out)|\≤ m. In the em lower-bounded min-sum-of-radii\nwith outliers ( lbksro) problem, the objective is to minimize \∑i\∈\nS\maxj\∈\σ-1(i)c(i,j), and in the em lower-bounded k-supplier\nwith outliers ( lbkso) problem, the objective is to minimize \maxi\∈\nS\maxj\∈\σ-1(i)c(i,j).\n We obtain an approximation factor of 12.365 for lbksro, which improves to\n3.83 for the non-outlier version (i.e., m=0). These also constitute the\n em first approximation bounds for the min-sum-of-radii objective when we\nconsider lower bounds and outliers em separately. We apply the primal-dual\nmethod to the relaxation where we Lagrangify the |S|\≤ k constraint. The\nchief technical contribution and novelty of our algorithm is that, departing\nfrom the standard paradigm used for such constrained problems, we obtain an\nO(1)-approximation em despite the fact that we do not obtain a\nLagrangian-multiplier-preserving algorithm for the Lagrangian relaxation. We\nbelieve that our ideas have broader applicability to other clustering problems\nwith outliers as well.\n We obtain approximation factors of 5 and 3 respectively for lbkso and\nits non-outlier version. These are the em first approximation results for\nk-supplier with em non-uniform lower bounds.\n