Improved approximation for prize-collecting red-blue median

Autor: Junyu Huang, Jianxin Wang, Feng Shi, Yutian Guo, Zhen Zhang
Rok vydání: 2021
Předmět:
Zdroj: Theoretical Computer Science. :67-82
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2021.05.029
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: