Approximation Algorithms For The Squared Metric Fault-tolerant Facility Placement Problem

The squared metric fault-tolerant facility placement problem which is a generalization of the squared metric facility location problem and fault-tolerant facility placement problem.We research this problem with a high practical value can help improve social productivity and economic efficiency.In this problem,we are given a set of locations F,a set of clients C.For each i ?F,j? C,we are allowed to open any number of facilities at each location i in which any unit facility with the same unit opening cost fi ? 0.And connecting one unit of demand from clients j to a facility at location i costs cij ? 0.For this problem,we assume that the unit connection cost is a squared metric.Each client j requires multiple facilities service for it which means that demands of any client j are rj>1.Some facilities that client j is connected to could be located at the same location,as long as they are all different and open.The objective is to find a F((?)F)in which open some facilities and satisfy the needs of each j such that minimize the total cost(including the opening cost and connection cost).We propose the squared metric fault-tolerant facility placement problem which is NP-hard.Under the assumption of P?NP,there is no exact algorithm in polynomial time.We usually design approximation algorithm to solve the problem which is NP-hard.The LP-rounding tech-nique is one of the most useful methods in approximation algorithm design.And we achieve a 10-approximation algorithm which is the first constant approximation algorithm applying LP-rounding technique which based on linear programming relaxation and dual programming.In the following,we achieve a 10-approximation algorithm employ LP-rounding technique which based on linear programming relaxation.Finally,we obtain an improved 9-approximation algo-rithm.