Approximation Algorithms For Dynamic,Robust And Capacity Constrained Facility Location

The facility location problem has been widely used in municipal engineering,telecommu-nication field,information retrieval,supply chain design and so on.It has been a hot topic in the field of combinatorial optimization since 60 s of the last century.The most classic type of the problem is the uncapacitated facility location problem.More specifically,there are a set of clients and a set of facilities,and their locations are given.There are opening cost for each facility and connection cost between the client and the facility.The goal is to identify facilities to be opened and to connect all the clients to the opened facilities.Because the facility loca-tion problem is NP-hard,accurate algorithm can not guarantee the calculation time.Though heuristic algorithms can get feasible solution in a short time,it is easy to fall into local optimum during the course for solving problems.The approximation ratio can not be obtained by theo-retical analysis.Normally,it is difficult to get the optimal solution.Therefore,approximation algorithm is an effective method.For the reason that facility location problems can be applied in many fields widely,many variants develop rapidly,such as k-median problem,capacitated facility location problem,ro-bust facility location problem,stochastic facility location problem,k-level facility location prob-lem,and so on.In this dissertation,several facility location problems are investigated.For each variant of the facility location problem,mathematical model is given,the approximation algo-rithm is devised and theoretical analysis is strictly deduced.For the facility location problem,when capacity constraints and cardinality constraints occur at the same time,the problem becomes more complicated.By far,there is no constant approximation algorithm for the case.For the non-uniform soft capacitated k-facility loca-tion problem,Lagrangian relaxation technique and stochastic algorithm are used to obtain a bi-criteria(20+5/n,25)-approximation algorithm,violating the capacity constraints.Specifi-cally,the target value corresponding to the solution of the algorithm does not exceed(20+5/n)times the optimal value under the condition that the capacity violation does not exceed 25 times the constraint.Compared with the known results,both the quality of the solution and the multi-ples of violation for the capacity have been greatly improved.As the variant of the metric uncapacitated facility location problem,the squared metric dynamic facility location problem is different from the following two aspects.The first is that the connection cost is squared metric,which does not satisfy the triangle inequalities.The second is that all facilities and clients appear in multiple-time periods.Combining the relationship between the connection cost and the distance in metric space,a 9-approximation algorithm can be obtained by primal-dual technique.In order to improve the quality of the solution further,relying on a revised instance in which the opening cost is scaled,a greedy technique can be used to get an improved 2.606-approximation algorithm.According to application background,many points show abnormal value in many opti-mization problems,which are called outliers.When they appear in the facility location prob-lem,the problem becomes robust facility location problem.In this dissertation,we research the robust dynamic facility location problem.Firstly,considering the unbounded integral gap,the instance is revised.Secondly,a primal-dual algorithm is used for the revised instance and the time when the dual variables stop increasing is selected reasonably.At last,the theoretical anal-ysis for 3-approximation is obtained.Based on the above work,an improved 2-approximation algorithm can also be obtained by greedy amplification technique.At the end of the dissertation,the squared metric lower-bounded sum of radii problem is discussed,which is also the variant of facility location problem.By primal-dual technique,La-grangian relaxation technique and properties of linear programming,we get the approximation solution of squared metric k-ball selection problem,which is the relaxation of the squared metric lower-bounded sum of radii problem.Then the relationship of the two problem is constructed.Finally,we get a(270+?)-approximation algorithm for the original problem.