带惩罚和次模结构的覆盖问题和设施选址问题的算法研究

发布时间：2018-06-19 11:07

本文选题：覆盖问题 + 设施选址问题　；参考：《北京工业大学》2016年博士论文

【摘要】：覆盖问题和设施选址问题是两类经典的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.
[Abstract]:The problem of coverage and facility location is the two kind of classical NP difficult problem. It has a wide range of practical application background. In recent years, it has become a hot topic in the field of approximate algorithm. This paper mainly studies several deformation of the covering problem and facility location problem from the angle of approximate algorithm, including the problem of the sub mode vertex cover with penalty, The penalty sub modular cost set covers the problem, the robust facility location problem with linear penalty, the priority facility location problem with the sub modular penalty. The first combinatorial approximate algorithm for the above problems is designed with the original dual technique and the algorithm analysis is given. The next two problems are further combined with the greedy augmentation techniques. Do not design an improved approximation algorithm and give an algorithm analysis. In the case of punishing submode vertex cover, each subset of the vertex set corresponds to a certain cover cost, and the cost function is a submodule function. For the edge set, if each edge corresponds to a certain linear penalty fee, it is called a submode vertex cover with linear penalty. Problem (SVCLP); if each subset of the set corresponds to a certain submode penalty cost, the sub mode vertex cover problem (SVCSP), called the submode penalty, is to select a top set to cover some edges, and to pay the corresponding penalty fee for the non covered edge, and finally make the sum of the cover cost and the penalty cost minimum. The mathematical programming model of the problem is presented. The original dual technique is applied directly to the linear programming relaxed dual programming of SVCLP and SVCSP, and the dual ascending process can not be controlled in polynomial time. In order to overcome this difficulty, we have relaxed the dual programming and analyzed the original dual 2- approximation algorithm of SVCLP respectively. The original dual 4- approximation algorithm with SVCSP. In a penalty submodular cost set coverage problem, each subset of the subsets corresponds to a certain cover cost and the cost function is a submodular function. For the set of elements, if each element corresponds to a certain linear penalty cost, it is called a submodular cost set with linear penalty. SCSCLP; if each subset of the set corresponds to a certain submode penalty cost, the submodular cost set coverage problem (SCSCSP) is called a subset of the subsets to cover a number of elements, and will pay the corresponding penalty cost for the non covered element, eventually making the cover cost and punishment. The sum of the sum of penalty costs is minimal. A mathematical programming model of the problem is given. Similarly, the original dual technique is applied directly to the linear programming relaxed dual programming of SCSCLP and SCSCSP, and the dual ascending process can not be controlled in polynomial time. In order to overcome this difficulty, we have relaxed the dual programming and analyzed and analyzed separately. The original dual ETA approximation algorithm of SCSCLP and the original dual 2 ETA approximation algorithm of SCSCSP. Among them, the maximum of the frequency that the element appears in the subset family is the maximum. In the robust facility location problem with linear penalty (RFLPLP), the exception and punitive value are considered, and the demand for some customers is not satisfied. Specifically, in RFLPLP The number of outliers is given, and each customer corresponds to a certain linear penalty cost. The goal is to select a set of set up facilities, connect a part of the customer to the set up, remove the abnormal customer, punish the remaining customers, eventually make the facility open, the connection between the customer and the facility, and the customer's punishment. The mathematical programming model of the penalty cost is given. The original dual approximation algorithm is designed for the special structure of the problem, and the approximate ratio is 3. Then the improved algorithm is designed and analyzed with the greedy augmentation technique, and the approximate ratio 3 is improved to the priority facility location problem with the second mode penalty (PFLPSP). At the same time, priority and submodel punitive are considered. Specifically, each customer in PFLPSP has a certain level of service level, and the cost of setting up each facility is an increasing function of the service level. The facilities that are connected to the customer must be opened and meet the customer's service level; every subset of the customer is a subset. The goal is to select a set of sub mode penalties. The goal is to select a set of facilities set up, and to select a set of punishing customers to connect the punishing customers to an open facility that meets the requirements of their service level, and ultimately make the facilities open, the connection costs between the customers and the facilities, and the customer's penalty cost. The mathematical programming model of the problem is given. Combining the priority of the problem and the sub modulus punitive, the original dual approximation algorithm is designed and the solution obtained is analyzed. The approximate ratio is 3. Then the improved algorithm is designed and analyzed with the greedy augmentation technique, and the approximate ratio is improved to 2.375..
【学位授予单位】：北京工业大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O224

【相似文献】