Approximation Algorithms For Priority Facility Location Problem With Penalties

Since facility location problem is one of the classical NP-hard problems, in the disser-tation, we consider the approximation algorithm of the priority facility location problemwith penalties, which is one of the variants of the facility location problem.We focus on the following two kinds of the variant problems. In the facility locationproblem with penalties, the demand of some clients is allowed to be not satisfied, but it willcause some penalties to these clients. In the priority facility location problem, each clienthas a level-of-service requirement, and each facility has a non-decreasing cost functionthat specifies the cost of opening this facility at the level-of-service.Combined with the above two variants of facility location problem, we discuss thepriority facility location problem with penalties, which equipped with the penalty and thelevel-of-service requirements. The object is to find a scheme: determine an opening facilityset, meanwhile select a penalized client set, and then connect the not penalized clients toan opening facility, such that the total cost, including the opening cost the connection costand the penalizing cost is minimized.According to the special structure of the problem, sorting the facilities in properorder, we design a primal-dual approximation algorithm, and analysis the algorithm toobtain the approximation factor3; applying the greedy augmentation procedure, scalingup the opening cost, and adding an opening facility with opening cost0for each client,converting the penalizing cost to connection cost, we present the improved algorithm, andthe performance factor3is further improved to1.8526.