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

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

带惩罚的容错设施布局问题的近似算法

在带惩罚的容错设施布局问题中,给定顾客集合、地址集合、以及每个顾客和各个地址之间的连接费用,这里假设连接费用是可度量的.每位顾客有各自的服务需求,每个地址可以开设任意多个设施,顾客可以被安排连接到某些地址的一些开设的设施上以满足其需求,也可以被拒绝,但这时要支付拒绝该顾客所带来的惩罚费用.目标是确定哪些顾客的服务需求被拒绝并开设一些设施,将未被拒绝的顾客连接到不同的开设设施上,使得开设费用、连接费用和惩罚费用总和最小.给出了带惩罚的容错设施布局问题的线性整数规划及其对偶规划,进一步,给出了基于其线性规划和对偶规划舍入的4-近似算法.