An Improved Approximation Algorithm for the Prize-Collecting Red-Blue Median Problem

摘要

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 for the 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 problem for the case where τ is a constant.