Local search algorithms for the red-blue median problem

M. Hajiaghayi, R. Khandekar, G. Kortsarz

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

In this paper, we consider the following red-blue median problem which is a generalization of the well-studied k-median problem. The input consists of a set of red facilities, a set of blue facilities, and a set of clients in a metric space and two integers kr,kb ≥0. The problem is to open at most kr red facilities and at most kb blue facilities and minimize the sum of distances of clients to their respective closest open facilities. We show, somewhat surprisingly, that the following simple local search algorithm yields a constant factor approximation for this problem. Start by opening any kr red and kb blue facilities. While possible, decrease the cost of the solution by closing a pair of red and blue facilities and opening a pair of red and blue facilities. We also improve the approximation factor for the prize-collecting k-median problem from 4 (Charikar et al. in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp. 642-641, 2001) to 3+ϵ, which matches the current best approximation factor for the k-median problem.

Original languageEnglish (US)
Pages (from-to)795-814
Number of pages20
JournalAlgorithmica
Volume63
Issue number4
DOIs
StatePublished - Aug 1 2012

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Facility location
  • Local search algorithms
  • Prize-collecting
  • k-median

Fingerprint

Dive into the research topics of 'Local search algorithms for the red-blue median problem'. Together they form a unique fingerprint.

Cite this