随机容错设施选址问题的原始-对偶近似算法

研究两阶段随机容错设施选址问题，其中需要服务的顾客在第二阶段出现（在第一阶段不知道）．两个阶段中每个设施的开设费用可以不同，设施的开设依赖于阶段和需要服务的顾客集合（称为场景）．并且在出现的场景里的每个顾客都有相同的连接需求，即每个顾客需要由r个不同的设施服务．给定所有可能的场景及相应的概率，目标是在两个阶段分别选取开设的设施集合，将出现场景的顾客连接到r个不同的开设设施上，使得包括设施费用和连接费用的总平均费用最小．根据问题的特定结构，给出了原始。对偶（组合）3-近似算法．

A primal-dual approximation algorithm for stochastic fault-tolerant facility location problem

In this paper, we consider the two-stage stochastic fault-tolerant facility location problem with uniform connectivity requirement where the clients to be served are only revealed at stage two （thus unknown at stage one）. The facilities may be opened at either stage, with possibly different opening costs, depending on the stage and the set of clients to be served （called a scenario）. Each client to be served in such a scenario has to be connected to r ≥1 distinct facilities. Given all possible scenarios and the corresponding probabilities, the objective is to determine two subsets of facilities to be opened at the two stages and to connect the clients in the realized scenario to r distinct opened facilities such that the total expected opening and connection cost is minimized. Based on the special structure of the problem, we offer a primal-dual （combinatorial） 3-approximation algorithm.