Approximation Algorithms For Multi-level And Stochastic Facility Location Problems

Facility location problem is one of the classical NP-hard problems in combinato-rial optimization which can not be solved in polynomial time, unless P=NP. Many NP-hard problems can be handled efficiently by approximation algorithms which output feasible solutions with estimated value in polynomial time. In this thesis, we consider the two-stage stochastic facility location problem, the two-stage stochastic facility lo-cation with linear penalties, the2-level facility location problem, and the k-level facility location problem with soft capacities.In Chapter2, we consider the two-stage stochastic facility location problem in which the client set depends on the realized scenario associated with the corresponding probability and the facility opening cost depends on the first/second stage. Our goal is to minimize the expected total cost including the facility opening cost and the connection cost. Instead of the usual approximation ratio, we consider the per-scenario bound which estimates quality for each realized scenario. Using linear programming rounding technique, we obtain the per-scenario bound2.3613.In Chapter3, we consider the stochastic facility location problem with linear penalties. In this problem, each client may be un-served which incurrs a penalty cost associated with this specified client. Our goal is to minimize the expected total cost including the facility opening cost, the connection cost, and the penalized cost. We propose a linear programming rounding3.0294-approximation algorithm.In Chapter4, we consider the2-level facility location problem in which each client must be served by two-level facilities. We present a primal-dual3(1+ε)-approximation algorithm, where ε is an arbitrary positive constant. Comparing with the standard primal-dual scheme, we use an approximated separation oracle technique to obtain a dual feasible solution. We further improve the approximation ratio to2.172(1+ε)2by adopting a greedy adjustment technique.In Chapter5, we consider the k-level facility location problem with soft capaci-ties. In this problem, the capacity of each facility can be increased multiply by paying the same multiple facility opening cost. Using the so-called bifactor reduction which estimates the desired approximation ratio via a bifactor of the k-level facility location problem, we obtain a5.5053-approximation algorithm.