论文部分内容阅读
本论文提出了一个新问题:随机的有相同连接需求的容错设施选址问题。在该问题中，给定设施集合F，顾客集合C，顾客与设施之间的连接费用c（c是度量的），在第二阶段中K个不同场景发生的概率p1,…，pK，在场景k中需要被连接的顾客集合Ck，在第一阶段开设设施i的费用f0i，在第二阶段场景k中开设设施i的费用fki，以及连接需求r.目标是决定开设一些设施，将每个顾客连接到满足连接需求的开设设施上，最终使得开设费用和连接费用的总体期望最小. 由于该问题是有度量的无容量设施选址问题的一个变形问题，所以它也是一个NP-难问题。设计近似算法是解决该难题的重要方法之一。第2章，我们介绍了随机的有相同连接需求的容错设施选址问题，并构造了该问题的整数规划，接着给出了它的松弛线性规划和对偶问题。第3章，描述了该问题的算法及算法分析。基于Jain和Vazirani针对无容量设施选址问题提出的原始对偶算法和Bumb针对容错设施选址问题给出的原始对偶算法，并结合随机的有相同连接需求的容错设施选址问题的特殊结构，解决了随机性和容错性带来的困难，本论文设计出了近似比为3的原始对偶算法，这是该问题的第一个近似算法。