Improved Approximation Algorithm for the Fault-Tolerant Facility Placement Problem with Rejection

摘要

In this article, we revisit an interesting variant of the fault-tolerant facility placement problem with rejection (FTFPWR, for short). In the FTFPWR, we are given a set of potential locations to open facilities, and a set of customers to be connected to a number of facilities to satisfy their demands. At each location we are allowed to open any number of facilities, each with its corresponding opening cost. Each customer has an integral demand which specifies the number of open facilities that it should be connected to. Some facilities that a customer is connected to could be located at the same location, as long as they are all different and open. For each location and customer pair we are also given a distance between them that represents the cost to connect one unit of demand from the customer to a facility at its location. We assume the distance function to be metric. The task is to choose a subset of locations to open facilities, and choose a subset of customers to connect their demands to the open facilities at locations with the remaining customers to be rejected by paying the rejection costs such that the sum of the facility opening costs, the connection costs, and the rejection costs is minimized. For the FTFPWR, the performance ratio of currently best approximation algorithm is 2.515. By introducing a randomized rounding approach and the derandomizing technique, we propose an improved approximation algorithm with the performance ratio of 2.07.