鲁棒和软容量设施选址与奖励-收集斯坦纳问题的近似算法

发布时间：2021-04-15 15:01

　　设施选址问题和奖励-收集斯坦纳树问题是计算机科学和运筹学领域中的经典问题,均有广泛的实际应用背景.本文通过设计近似算法,对设施选址问题和奖励-收集斯坦纳树问题的几种变形进行研究,包括:鲁棒设施租赁问题,平方度量的软容量设施选址问题,k-奖励-收集斯坦纳树问题,广义奖励-收集斯坦纳森林问题.基于原始对偶技巧,我们分别给出上述变形问题的近似算法和相应的算法分析.在鲁棒设施租赁问题中,给定设施集合,基数为n的顾客集合,时间段集合和非负整数q<n.每个时间段都有相应的顾客子集到达.每个设施有一种或多种租赁类型,每种租赁类型给定相应的租赁长度.在某个时间段以某种类型租赁某个设施会产生租赁费用,且被租赁的设施会从此时间段起以相应的租赁长度为时长被租赁.连接顾客到设施会产生连接费用,连接费用等于顾客与设施之间的距离.每个顾客子集中的顾客只能被连接到它到达时被租赁的某个设施.在连接费用满足非负性,对称性,和三角不等式的假设下,目标是租赁一些设施,连接至少n-q个顾客,使得租赁费用与连接费用之和最小.解决此问题的难点在于鲁棒设施租赁问题自然的线性规划松弛的整数间隙是无界的.为了克服这个难点,我们根... 

【文章来源】：北京工业大学北京市 211工程院校

【文章页数】：85 页

【学位级别】：博士

【部分图文】：

图３－１断言证明的示意图．??Ｆｉｇ．?３－１?Ｉｌｌｕｓｔｒａｔｉｏｎ?ｏｆ?ｔｈｅ?ｃｌａｉｍ．??

时的７值．可得，??ａ］ｔ?＾?ｍｉｎ｛７（ｉ，ｆｃ）Ｓ），７（ｉ，ｆｃ，ｓ）｝?＜?ｌ（ｉ，ｋ，ｓ）?＜?ａｊｔ－??由于连接费用满足三角不等式（参见图３－２），我们结合情形１和情形２，此引理??得证．??°ｉｊ?—?ｃｉｊ?＋?ｃｉｊ?＋?ｃＴｊ?—?ａｊｔ?＋?＾ａｊｔ?—?＾ａｊｔ?＝?３ａｊｔ．??结合情形１和情形２，此引理得证．?口??用Ｘ表示设施集合｛（ｉ＇，ｆｃ＇，Ｓ＇），（＆，彳Ｓ／）｝，其中设施（ｉ＇，ｆｃ＇，ｓ＇）是实例ＺＡＴ的??最优解中租赁费用最大的设施．设施是算法最终临时租赁的设施．用Ｘ??表示与Ｘ相关的被租赁的设施．即，??文：二?Ｕ?＊＾，Ｍ．??（ｉ，ｋ＾ｓ）ｅＸ??用Ｆ表示文中设施的租赁费用．下面的引理给出租赁费用Ｆ的上界．??引理３．３??Ｆ?＜３?ａ］ｔ－??（ｊ，ｔ）ｅｖ??证明只有公ｄ中顾客可对Ｘ中设施做贡献．对任意设施（ｉ，ｆｃ，ｓ）?Ｇ元用表??示所有对做贡献的顾客？即

＋?（４＿５）??由于距离是度量的（参见图４－１），我们有??Ｃｊ／?ｊ?—?ｄｉｆ?ｊ??＾?＋?ｄｗｉｔ＾ｊ）??一?＂Ｉ－＾ｗｉｔＱ）＾）＾ｗｉｔ＾＇）＾??—ｄ＾ｊｆ２?＋?ｄｗｉｔ＾ｊｆ２?＋?ｃ２ｄｉｆｊｆｄｗｉｔ＾ｊ／?＋?ｄｗｉｔ＾－＾２?＋?２（ｄ＾＾／?＋?ｄｗｉｔ＾＾ｖ）ｄｗｉｔ＾＾??＜?３（ｄｉｆｊｆ）２?＋?３（ｄｗｉｔ（＾－／）２?＋?３（ｄｗｉｔ（＾－）２??—＾ｃ＾ｊｆ?＋?３ｃｗｉｔ＾ｊｆ?＋?３ｃｗｉｔ＾－＾－．?（４－６）??因为顾客／对设施《和设施ｗｉｔ（ｊ）都做贡献，所以ｃ＃?＋?９／ｙ／ｌＯｉｖ?ｇ?和??ｃｗｉｔＷ／?Ｓ?％成立．由算法３，可得％?ｇ?ｔｗｉｔ⑴＝％．结合不等式（４－５）和不等式??（４－６），有??９ｆａ（Ｊ）?９ｆｉ，??ｃ＜ｒ（ｊ）ｊ?＋?１〇ｕ?＾?＾?３ｃ＾ｙ?＋??（?９／ｉ／?＼?．?．??３?＋?ｉ〇＾?ｉ?＋?３Ｃｗｉｔ（ｉ）＾?＋?３ｃｗｉ？ｉ）ｉ??＾?３（Ｘｊｆ?＋?＾ＯＬｊｆ?＋?Ｓｃｋｊ??＜?９ａｊ??＝ＱａＣｊ．??此引理得证．，?□??有了以上引理，我们可以分析出算法所得解的费用与最优解费用的关系，给出??－３２－?


本文编号：3139560