Parity-Constrained Weighted k-Center

This paper studies the parity-constrained weighted k-center (PARW k-center) problem. In the PARW k-center problem, we are given a set of vertices in a metric space with distances and a non-negative budget k. Additionally, each vertex is associated with a non-negative weight and an odd or even parity requirement. The objective is to select a subset of vertices as open centers and assign each vertex to an open center so as to minimize the maximum distance of any vertex to its assigned center, but subject to that the total weight of all open centers is no more than k, and that the number of vertices assigned to each open center meets its parity requirement. As our main contribution, we present a 10-approximation algorithm for the PARW k-center problem, which consists of three main phases. The first phase utilizes the concept of maximal independent set to initially determine a solution (i.e., determine a set of open centers and assignments of all the vertices) whose total weight of open centers does not exceed the budget k. By pairing open centers that do not meet their parity requirements under the initial assignments, the second and third phases respectively modify the open centers and assignments, leading to a feasible solution.