Improved Approximation for Prize-Collecting Red-Blue Median
Improved Approximation for Prize-Collecting Red-Blue Median
复制标题
改进了收集奖品的红蓝中位数的近似值
DOI：
10.1016/j.tcs.2021.05.029
复制
发表时间：
2021-07
影响因子：
1.1
通讯作者：
Feng Shi
中科院分区：
文献类型：
--
作者：
Zhen Zhang;Yutian Guo;Junyu Huang;Jianxin Wang;Feng Shi
The red-blue median problem considers a set of red facilities, a set of blue facilities, and a set of clients located in some metric space. The goal is to open k r red facilities and k b blue facilities such that the sum of the distance from each client to its nearest opened facility is minimized, where k r, k b≥ 0 are two given integers. Designing approximation algorithms for this problem remains an active area of research due to its applications in various fields. However, in many applications, the existence of noisy data poses a big challenge for the problem. In this paper, we consider the prize-collecting red-blue median problem, where the noisy data can be removed by paying a penalty cost. The current best approximation guarantee for the prize-collecting red-blue median problem is a ratio of 24, which was obtained by LP-rounding. We deal with this problem using a local search algorithm. We construct a layered structure of the swap pairs, which yields a (9+ ϵ)-approximation for the prize-collecting red-blue median problem. Our techniques generalize to a more general prize-collecting τ-color median problem, where the facilities have τ different types, and give a (4 τ+ 1+ ϵ)-approximation for the case where τ is a constant.
登录
查看更多内容
DOI：
--
发表时间：
2001-01
期刊：
--
影响因子：
--
作者：
M. Charikar;S. Khuller;D. Mount;G. Narasimhan
通讯作者：
M. Charikar;S. Khuller;D. Mount;G. Narasimhan
DOI：
10.1145/950620.950621
发表时间：
2002-07
期刊：
ArXiv
影响因子：
--
作者：
K. Jain;Mohammad Mahdian;E. Markakis;A. Saberi;V. Vazirani
通讯作者：
K. Jain;Mohammad Mahdian;E. Markakis;A. Saberi;V. Vazirani
影响因子：
1.1
作者：
M. Hajiaghayi;R. Khandekar;G. Kortsarz
通讯作者：
M. Hajiaghayi;R. Khandekar;G. Kortsarz
DOI：
10.1007/978-3-642-15775-2_27
发表时间：
2010-09
期刊：
--
影响因子：
--
作者：
M. Hajiaghayi;R. Khandekar;G. Kortsarz
通讯作者：
M. Hajiaghayi;R. Khandekar;G. Kortsarz
DOI：
10.1145/3477541
发表时间：
2018-12
期刊：
ArXiv
影响因子：
--
作者：
Vincent Cohen-Addad;A. Feldmann;David Saulpic
通讯作者：
Vincent Cohen-Addad;A. Feldmann;David Saulpic