Local Search Algorithms for the Red-Blue Median Problem
Local Search Algorithms for the Red-Blue Median Problem
复制标题
DOI：
10.1007/s00453-011-9547-9
复制
发表时间：
2012-08
期刊：
影响因子：
1.1
通讯作者：
M. Hajiaghayi;R. Khandekar;G. Kortsarz
中科院分区：
文献类型：
--
作者：
M. Hajiaghayi;R. Khandekar;G. Kortsarz
在本文中，我们考虑以下红蓝中值问题，它是经过充分研究的 k 中值问题的推广。输入由度量空间中的一组红色设施、一组蓝色设施和一组客户端以及两个整数 skr,kb≥0 组成。问题是打开最多 krred 设施和最多 kbblue 设施，并最小化客户端到各自最接近的开放设施的距离总和。我们表明，有些令人惊讶的是，以下简单的本地搜索算法为该问题产生了常数因子近似值。首先打开任何 krred 和 kbblue 设施。在可能的情况下，通过关闭一对红色和蓝色设施并打开一对红色和蓝色设施来降低解决方案的成本。我们还将奖品收集 k 中值问题的近似因子从 4（Charikar 等人，在 ACM-SIAM 离散算法研讨会论文集，第 642-641 页，2001 年）改进为 3+ϵ，这与当前的最佳近似值相匹配因数 k中值问题。
In this paper, we consider the followingred-blue medianproblem which is a generalization of the well-studiedk-medianproblem. The input consists of a set ofredfacilities, a set ofbluefacilities, and a set of clients in a metric space and two integerskr,kb≥0. The problem is to open at mostkrred facilities and at mostkbblue 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 anykrred andkbblue 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 theprize-collectingk-medianproblem 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 thek-median problem.