The Approximation Algorithms For Stochastic?Fault-tolerant And Multi-level Facility Location Problems

Facility location problem was formally proposed by an American researcher named Coop-er in 1960's.It has a wide variety of applications in such areas as regional planning,economic management,communication,computer science,warehouse selection and supply chain man-agement.Modern day applications also includes the placement of proxy servers on the web.Therefore,it has occupied a central place in operation research in recent forty years and more and more researchers in operation research,management and computer science have been ab-sorbed to this erea.The most classical facility location problem is the metric uncapacitated facility location problem(UFLP)which has been widely investigated for several decades.In this problem,there is a set of locations where facilities can be built with an associated nonnega-tive fixed open cost.There is also a set of clients who require service from an open facility with an associated nonnegative connection cost.The objective is to decide a subset of locations at which to open facilities and assignment of each client to some open facility so that the overall open cost and connection cost is minimized.This can be described by a simple integer linear program which can be easily analyzed.But it is NP-hard.Therefore,designing approximation algorithms using some schemes is the best way to cope with it.The main schemes in designing approximation algorithms include the primal-dual,LP-rounding and local search.The metric mainly means that the connection cost satisfies the triangle inequality.The case that the square of the connection cost satisfies triangle inequality is also investigated recently.Although the structure of the formulation for UFLP is simple,it can not be applied in re-ality directly.Therefore,many variant of the UFLP have been introduced in recent decades.We mainly study the following variant of the UFLP:the fault-tolerant stochastic facility placement problem,the risk-adjusted two-stage stochastic facility location problem with penalty,the square metric K-level facility location problem,the square metric K-level soft capacitated facility loca-tion problem and the warehouse-retailer network design game.All these are NP-hard.The main technique we use to design the approximation algorithms for these problems is LP-rounding.The classical two-stage stochastic facility location problem considers the case that the in-formation of the client is uncertain.In this problem there is a set of location on which to open facilities,and a set of finite scenarios each of which has the specified facilities and clients.The uncertainty of the scenarios is modeled by a probability distribution over the possible realiza-tions of the actual data.In the first stage we would like to choose a subset of locations to open facilities.In the second stage we plan to open a subset of facilities in each scenario and connect each client to an open facility opened in the first stage or the second stage but in the correlated scenario.Usually the open cost in the second stage is a little bit more expensive than that in the first stage.The final object is to minimize the total expected facility open cost and the ex-pected connection cost.The two-stage stochastic facility placement problem is different from the two-stage stochastic facility location problem in that the former can open arbitrarily any number of facilities at any location.We combine the approximation algorithms of the two-stage stochastic facility location problem and the fault-tolerant facility placement problem to obtain a LP-rounding 5-approximation algorithm.By introducing risk aversion parameter we obtain the risk-adjusted stochastic facility lo-cation problem.The difference is that we choose a finite number of scenarios with SAA method in the second stage so that the cost in this stage is related to the given risk aversion parameter.If we allow some distant client to reject to connect any open facility,we obtain the risk-adjusted two-stage stochastic facility location problem with penalty.We will give the formulation,LP-rounding approximation algorithm and prove its ratio is 6.In multi-level facility location problem We study the square metric K-level facility location problem and the square metric soft capacitated K-level facility location problem.Both of these problem consider the case that the locations are in K-level.Each client must connect to k open facilities in K different level.The latter gives an soft capacity constraint to each facility so that the number of clients connected to an open facility cannot exceed the facility's capacity.By reanalyzing the known LP-rounding approximation algorithms for the two problems under the condition that the cost form a square metric,we prove the ratio is 9 and 12.2216,respectively.The warehouse-retailer network design problem,which is the main topic in marketing for large corporation in modern market-oriented economy,is another variant of UFLP.We consider the warehouse-retailer network design game(WRND)based on this problem.In WRND,a fi-nite set of retailers is given,and the demand each retailer faces is assumed to be deterministic at a constant rate.There exist an external supplier and also a finite set of potential warehouse locations.we aim to choose a subset of warehouses to locate,assign each retailer to an open warehouse,and determine the warehouse-retailer echelon inventory replenishment policies so that the total warehouse location,transportation,and two-echelon inventory costs is minimized.By carefully defining the generalized distance function,we present a cost-sharing method for the warehouse-retailer network design game.We show that the proposed cost-sharing scheme is cross-monotonic,competitive,and 3-approximate cost recovery.