License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.29
URN: urn:nbn:de:0030-drops-90335
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9033/
Go to the corresponding LIPIcs Volume Portal

Chakrabarty, Deeparnab ; Swamy, Chaitanya

Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Median

pdf-format:
LIPIcs-ICALP-2018-29.pdf (0.5 MB)

Abstract

We consider a generalization of k-median and k-center, called the ordered k-median problem. In this problem, we are given a metric space (D,{c_{ij}}) with n=|D| points, and a non-increasing weight vector w in R_+^n, and the goal is to open k centers and assign each point j in D to a center so as to minimize w_1 *(largest assignment cost)+w_2 *(second-largest assignment cost)+...+w_n *(n-th largest assignment cost). We give an (18+epsilon)-approximation algorithm for this problem. Our algorithms utilize Lagrangian relaxation and the primal-dual schema, combined with an enumeration procedure of Aouad and Segev. For the special case of {0,1}-weights, which models the problem of minimizing the l largest assignment costs that is interesting in and of by itself, we provide a novel reduction to the (standard) k-median problem, showing that LP-relative guarantees for k-median translate to guarantees for the ordered k-median problem; this yields a nice and clean (8.5+epsilon)-approximation algorithm for {0,1} weights.

BibTeX - Entry

@InProceedings{chakrabarty_et_al:LIPIcs:2018:9033,
  author =	{Deeparnab Chakrabarty and Chaitanya Swamy},
  title =	{{Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Median}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{29:1--29:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9033},
  URN =		{urn:nbn:de:0030-drops-90335},
  doi =		{10.4230/LIPIcs.ICALP.2018.29},
  annote =	{Keywords: Approximation algorithms, Clustering, Facility location, Primal-dual method}
}

Keywords: Approximation algorithms, Clustering, Facility location, Primal-dual method
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI