The Algorithms For Covering Problems And Facility Location Problems With Penalties And Submodularities

Covering and facility location problems are classical NP-hard problems of broad practical applications. They have attracted a lot of attentions in recent years in the terms of approxima-tion algorithms. In this dissertation, we consider approximation algorithms for various covering and the facility location problems, including the submodular vertex cover problems with penal-ties, the submodular cost set cover problems with penalties, the robust facility location problem with linear penalties, and the priority facility location problem with submodular penalties. We offer the first primal-dual methods with constant approximation ratios for these problems, re-spectively. For the last two problems, we also provide improved approximation algorithms by combining the greedy augmentation technique.In the submodular vertex cover problems with penalties, each subset of the vertex set has a submodular covering cost and each edge has a penalty cost. Two versions may arise, namely the submodular vertex cover problem with linear edge penalties (SVCLP) and the submodular vertex cover problem with submodular edge penalties (SVCSP). The objective in each problem is to select a vertex subset to cover some edges and penalize the uncovered edges such that the total covering and penalty cost is minimized. Applying the primal-dual framework directly on the dual programs of their linear program relaxations for the SVCLP and SVCSP cannot guarantee that the dual ascending process terminates in polynomial time. To overcome this difficulty, we relax these two dual programs to slightly weaker versions, leading to primal-dual 2-approximation algorithm for the SVCLP and 4-approximation algorithm for the SVCSP, respectively.In the submodular cost set cover problems with penalties, each subset in the family of subsets has a submodular covering cost. Two versions may arise, namely the submodular set cover problem with linear edge penalties (SCSCLP) and the submodular set cover problem with submodular edge penalties (SCSCSP). The objective in each problem is to select subsets from the family of subsets to cover some elements and penalize the uncovered elements such that the total covering and penalty is minimized. Similarly, applying the primal-dual framework directly on the dual programs of their linear program relaxations for the SVCLP and SVCSP cannot guarantee that the dual ascending process terminates in polynomial time. To overcome this difficulty, we relax these two dual programs to slightly weaker versions, leading to the primal-dual η-approximation algorithm for the SCSCLP and the primal-dual 2η-approximation algorithm for the SCSCSP, respectively, where η is the largest number of sets that each element belongs to.In the robust facility location problem with linear penalties (RFLPLP), we consider both the possibility of outliers and penalty, where the demand of some clients may not be met. Specif-ically, in the RFLPLP the number of outliers is given, and each client has a linear penalty cost. The objective is to determine an opening facility set, connect some of the clients to opening fa-cilities, ignore the outlier clients, and penalize the remaining clients, such that the total facility opening cost, the connection cost and the penalty cost is minimized. By exploiting the special structure of the problem, we design a primal-dual approximation algorithm with approximation factor 3, which is improved to 2 by combining the greedy augmentation procedure.In the priority facility location problem with submodular penalties (PFLPSP), we con-sider both the priority and submodular penalty. Specifically, in the PFLPSP each client has a service-level requirement, and each facility has a non-decreasing cost function with respect to the Service-level. An open facility must satisfy the requirement of the clients served by it, and each subset of the clients has a submodular penalty cost. The objective is to determine an opening facility set, select a penalized client set, and then connect the non-penalized clients to the opening facilities that satisfy the requirement of the service-level, such that the total fa-cility opening cost, connection cost and submodular penalty cost is minimized. According to the priority and submodular penalty, we design a primal-dual approximation algorithm with an approximation factor 3; which is improved to 2.375 by combining the greedy augmentation pro-cedure.