随机容错设施布局问题的近似算法(英文)

An Approximation Algorithm for the Stochastic Fault-Tolerant Facility Placement Problem

在确定性的容错设施布局问题中,给定顾客的集合和地址的集合.在每个地址上可以开设任意数目的不同设施.每个顾客j有连接需求r_j.允许将顾客J连到同一地址的不同设施上.目标是开设一些设施并将每个顾客j连到r_j个不同的设施上,使得总开设费用和连接费用最小.研究两阶段随机容错设施布局问题(SFTFP),顾客的集合事先不知道,但是具有有限多个场景并知道其概率分布.每个场景指定需要服务的顾客的子集.并且每个设施有两种类型的开设费用.在第一阶段根据顾客的随机信息确定性地开设一些设施,在第二阶段根据顾客的真实信息再增加开设一些设施.给出随机容错布局问题的线性整数规划和基于线性规划舍入的5-近似算法.

In the deterministic fault-tolerant facility placement problem （FTFP）, we are given a set of locations and a set of clients. We can open any number of different facilities with the same opening cost at each location. Each client j has an integer requirement rj. Connecting client j to different facilities at the same location is permitted. The objective is to open some facilities and connect each client j to rj different facilities such that the total cost is minimized. In this paper, we consider the two-stage stochas- tic fault-tolerant facility placement problem （SFTFP） with recourse in which the set of clients are unknown in advance. But there are finite scenarios materialized by a proba- bility distribution. Each scenario specifies a subset of clients to be assigned. Moreover, each facility has two kinds of opening cost. In the first stage, we open a subset of facilities according to the stochastic information of the clients. In the second stage, we can open additional number of facilities when the actual information of the clients is revealed. We give a linear integral program and an LP-rounding based 5-approximation algorithm for the SFTFP.