The Algorithm Research Of Stochastic, Fault-tolerant And Obnoxious Facility Location

The facility location problem has occupied a central place in operationsresearch since1960s. The uncapacitated facility location problem is the mostclassical facility location problem. It has been proved that it is NP-hard. Inthis dissertation, we study some variants of uncapacitated facility locationproblem from the perspective of approximation algorithm.In this dissertation, we consider several variants of uncapacitated facil-ity location problem, the fault-tolerant concave facility location problem withuniform requirements, the stochastic facility location problem with serviceinstallation costs, the facility location problem with submodular penaltiesand stochastic demands, the facility location problem with soft capacitiesand stochastic demands and the obnoxious facility game in a metric space.About these problems, we design approximation algorithms and get results byalgorithm analysis.For the fault-tolerant concave facility location problem with uniform re-quirements, we give a dual-fitting algorithm. And we achieve a1.61approxi-mation factor and a (1.11,1.78) approximation bifactor by algorithm analysis.Then based on the dual-fitting algorithm, combing scaling and greedy augmen-tation, we present another algorithm and the approximation factor is improvedto1.52. For the stochastic facility location problem with service installationcosts, when all the service installation costs are based on an assumption, wegive a7-approximation algorithm using primal-dual method. For the facil-ity location problem with submodular penalties and stochastic demands, wepropose a primal-dual approximation algorithm and obtain3approximationfactor. For the facility location problem with soft capacities and stochasticdemands, a primal-dual approximation algorithm is designed and showed theapproximation factor is6.For the obnoxious facility game in a metric space, we propose a group strategy-proof deterministic mechanism with an approximation factor3, alsoproviding the lower bound of any group strategy-proof deterministic mecha-nism is no less than3. Then we obtain a group strategy-proof randomizedmechanism, achieving an approximation factor32. Later, we extend the ob-noxious facility game in a metric space to general case in which all facilities aredefined on an assumption. For this general case, we get a group strategy-proofdeterministic mechanism, yielding an approximation factor3.At last, we specify a few critical problems to be resolved, such as, im-proving the upper bound of the uncapacitated facility location problem, ap-proximation algorithm design for fault-tolerant concave facility location(all therequirements of clients are not uniform), the approximation algorithm for thegeneral obnoxious facility game in a metric space and so on.