Approximation Algorithms For The Robust And Soft Capacitated Facility Location Problem And The Prize-collecting Steiner Problem

Both the facility location problem and the prize-collecting Steiner tree problem are classi-cal problems in computer science and operations research,and have extremely broad practical applications.By designing approximation algorithms,this dissertation studies several variants of the facility location problem and the prize-collecting Steiner tree problem,including the ro-bust facility leasing problem,the squared metric soft capacitated facility location problem,the k-prize-collecting Steiner tree problem,and the generalized prize-collecting Steiner forest prob=lem.Based on the technique of primal-dual,we propose approximation algorithms alongside analyses for the variants.In the robust facility leasing problem,a facility set,a client set of cardinality n,time period set and a non-negative integer q<n are given.At each time period,a subset of clients arrives.Every facility has one or more lease types,and a lease length is also given for any lease type.Leasing some facility of some type at some time period incurs a leasing cost,and this facility is leased from the time period for the duration of the time length.Connecting a client to a facility incurs a connection cost which is equal to the distance of this facility-client pair.Every client can only be connected to a facility whose leased interval contains the arrival time of the client.Under the assumption that the connection costs are non-negative,symmetric and satisfy the triangle inequality,our goal is to lease some facilities,connect at least n-q clients such that the total cost including leasing costs and connection costs is minimized.The crucial challenge of solving this problem is that the natural linear program relaxation of the robust facility leasing problem has an unbounded integrality gap.In order to overcome this challenge,we construct a new instance with bounded integrality gap,which is based on the original instance of the problem,and apply primal-dual technique for the new instance to present a 6-approximation algorithm for the robust facility leasing problem.By modifying the phase of constructing an integer primal feasible solution in the above algorithm,we further propose an improved 3-approximation algorithm.In the squared metric soft capacitated facility location problem,a facility set and a client set are given.Every facility i has a capacity ui and an opening cost fi,and can be opened once or multiple times.If facility i is opened l times,it can be connected by at most lui clients and incurs an opening cost of lfi.Connecting a client to a facility incurs a connection cost which is equal to the square of the distance of this facility-client pair.Under the assumption that the distances are non-negative,symmetric and satisfy the triangle inequality,our aim is to open some facilities(once or multiple times)and connect every client to an opened facility without violating the capacity constraint,such that the total cost including opening costs as well as connection costs is minimized.The difficulty of solving this problem is that the connection costs do not satisfy the triangle inequality.By exploring the property of squared metric problems,we overcome the difficulty and propose a 10-approximation algorithm for the squared metric soft capacitated facility location problem.In the k-prize-collecting Steiner tree problem,a connected graph,a root and an integer k are given.Every edge has a connection cost,and every vertex has a penalty cost.The goal is to find an r-rooted tree that spans at least k vertices,such that the sum of the connection costs of the edges in the tree and the penalty costs of the vertices not spanned by the tree is minimized.The challenge of solving this problem is that we must find a tree which spans at least k vertices.By using the primal-dual 2-approximation algorithm for the prize-collecting Steiner tree problem as a subroutine and combining the technique of Lagrangean relaxation,we conquer the challenge and obtain a 5-approximation algorithm for the k-prize-collecting Steiner tree problem.In the generalized prize-collecting Steiner forest problem,a connected graph and a set of vertex sets V={Vi,V2,…,Vl} are given.Every edge has a connection cost,and every vertex set has a penalty cost.For any edge set F,vertex set Vi is said to be spanned by F if Vi is in a connected component of F.The aim is to find an edge set,such that the sum of the connection costs of the edges in the edge set and the penalty costs of the vertex sets not spanned by the edge set is minimized.The difficulty of solving this problem is that some dual variables may contribute to both the connection costs and the penalty costs during the natural dual ascending process.In order to conquer the difficulty,we bound the connection costs and the penalty costs separately with the dual objective value and get a 3-approximation algorithm.