论文部分内容阅读
覆盖问题和设施选址问题是两类经典的NP难解问题,有广泛的实际应用背景,近年来已成为近似算法领域的研究热点.本文主要从近似算法的角度对覆盖问题和设施选址问题的几个变形进行了研究,包括：带惩罚的次模顶点覆盖问题,带惩罚的次模费用集合覆盖问题,带线性惩罚的鲁棒设施选址问题,带次模惩罚的优先设施选址问题.应用原始对偶技巧,分别设计了上述问题的第一个组合近似算法且给出了算法分析.对于后两个问题,又进一步结合贪婪增广技巧,分别设计了改进的近似算法且给出了算法分析.在带惩罚的次模顶点覆盖问题中,顶点集的每个子集都对应一定的覆盖费用,且该费用函数为次模函数.对于边集,若每条边都对应一定的线性惩罚费用,则称为带线性惩罚的次模顶点覆盖问题(SVCLP);若边集的每个子集都对应一定的次模惩罚费用,则称为带次模惩罚的次模顶点覆盖问题(SVCSP)目标是选择一个顶点子集来覆盖一些边,对于没有被覆盖的边将支付相应的惩罚费用,最终使得覆盖费用和惩罚费用之和最小.给出了问题的数学规划模型.将原始对偶技巧直接应用到SVCLP和SVCSP的线性规划松弛的对偶规划上,并不能在多项式时间内控制对偶上升过程.为了克服这一困难,我们将对偶规划进行了松弛,分别设计并分析了SVCLP的原始对偶2-近似算法和SVCSP的原始对偶4-近似算法.在带惩罚的次模费用集合覆盖问题中,子集族中的每个子集都对应一定的覆盖费用,且该费用函数为次模函数.对于元素集合,若每个元素都对应一定的线性惩罚费用,则称为带线性惩罚的次模费用集合覆盖问题(SCSCLP);若元素集合的每个子集都对应一定的次模惩罚费用,则称为带次模惩罚的次模费用集合覆盖问题(SCSCSP)目标是从子集族中选择子集来覆盖一些元素,对于没有被覆盖的元素将支付相应的惩罚费用,最终使得覆盖费用和惩罚费用之和最小.给出了问题的数学规划模型.类似的,将原始对偶技巧直接应用到SCSCLP和SCSCSP的线性规划松弛的对偶规划上,并不能在多项式时间内控制对偶上升过程.为了克服这一困难,我们将对偶规划进行了松弛,分别设计并分析了SCSCLP的原始对偶η-近似算法和SCSCSP的原始对偶2η-近似算法.其中,叼为元素在子集族中出现的频率的最大值.在带线性惩罚的鲁棒设施选址问题(RFLPLP)中,同时考虑了异常值和惩罚性,允许一些顾客的需求不被满足.具体来讲,RFLPLP中异常值的个数是给定的,且每个顾客都对应一定的线性惩罚费用.目标是选择一个开设的设施集合,将一部分顾客连接到开设的设施,排除异常值顾客,惩罚剩下的顾客,最终使得设施开设费用,顾客与设施之间的连接费用以及顾客的惩罚费用之和最小.给出了问题的数学规划模型.针对该问题的特殊结构,设计了原始对偶近似算法,分析得到的近似比为3；之后结合贪婪增广技巧,设计并分析了改进的算法,将近似比3改进到2.在带次模惩罚的优先设施选址问题(PFLPSP)中,同时考虑了优先性和次模惩罚性.具体来讲,PFLPSP中每个顾客都有一定的服务水平要求,并且每个设施的开设费用是关于服务水平的递增函数,与顾客相连接的设施必须是开设的且能够满足顾客的服务水平要求；顾客的每个子集都对应一定的次模惩罚费用.目标是选择一个开设的设施集合,且选择被惩罚的顾客集合,将未被惩罚的顾客连接到能够满足其服务水平要求的开设设施上,最终使得设施开设费用,顾客与设施之间的连接费用以及顾客的惩罚费用之和最小.给出了问题的数学规划模型.结合问题的优先性和次模惩罚性,设计了原始对偶近似算法,并对算法得到的解进行了分析,得到的近似比为3；之后结合贪婪增广技巧,设计并分析了改进的算法,将近似比3改进到了2.375.