本文選題：覆蓋問題 + 設(shè)施選址問題　； 參考：《北京工業(yè)大學(xué)》2016年博士論文

【摘要】：覆蓋問題和設(shè)施選址問題是兩類經(jīng)典的NP難解問題,有廣泛的實(shí)際應(yīng)用背景,近年來已成為近似算法領(lǐng)域的研究熱點(diǎn).本文主要從近似算法的角度對覆蓋問題和設(shè)施選址問題的幾個變形進(jìn)行了研究,包括：帶懲罰的次模頂點(diǎn)覆蓋問題,帶懲罰的次模費(fèi)用集合覆蓋問題,帶線性懲罰的魯棒設(shè)施選址問題,帶次模懲罰的優(yōu)先設(shè)施選址問題.應(yīng)用原始對偶技巧,分別設(shè)計了上述問題的第一個組合近似算法且給出了算法分析.對于后兩個問題,又進(jìn)一步結(jié)合貪婪增廣技巧,分別設(shè)計了改進(jìn)的近似算法且給出了算法分析.在帶懲罰的次模頂點(diǎn)覆蓋問題中,頂點(diǎn)集的每個子集都對應(yīng)一定的覆蓋費(fèi)用,且該費(fèi)用函數(shù)為次模函數(shù).對于邊集,若每條邊都對應(yīng)一定的線性懲罰費(fèi)用,則稱為帶線性懲罰的次模頂點(diǎn)覆蓋問題(SVCLP);若邊集的每個子集都對應(yīng)一定的次模懲罰費(fèi)用,則稱為帶次模懲罰的次模頂點(diǎn)覆蓋問題(SVCSP)目標(biāo)是選擇一個頂點(diǎn)子集來覆蓋一些邊,對于沒有被覆蓋的邊將支付相應(yīng)的懲罰費(fèi)用,最終使得覆蓋費(fèi)用和懲罰費(fèi)用之和最小.給出了問題的數(shù)學(xué)規(guī)劃模型.將原始對偶技巧直接應(yīng)用到SVCLP和SVCSP的線性規(guī)劃松弛的對偶規(guī)劃上,并不能在多項(xiàng)式時間內(nèi)控制對偶上升過程.為了克服這一困難,我們將對偶規(guī)劃進(jìn)行了松弛,分別設(shè)計并分析了SVCLP的原始對偶2-近似算法和SVCSP的原始對偶4-近似算法.在帶懲罰的次模費(fèi)用集合覆蓋問題中,子集族中的每個子集都對應(yīng)一定的覆蓋費(fèi)用,且該費(fèi)用函數(shù)為次模函數(shù).對于元素集合,若每個元素都對應(yīng)一定的線性懲罰費(fèi)用,則稱為帶線性懲罰的次模費(fèi)用集合覆蓋問題(SCSCLP);若元素集合的每個子集都對應(yīng)一定的次模懲罰費(fèi)用,則稱為帶次模懲罰的次模費(fèi)用集合覆蓋問題(SCSCSP)目標(biāo)是從子集族中選擇子集來覆蓋一些元素,對于沒有被覆蓋的元素將支付相應(yīng)的懲罰費(fèi)用,最終使得覆蓋費(fèi)用和懲罰費(fèi)用之和最小.給出了問題的數(shù)學(xué)規(guī)劃模型.類似的,將原始對偶技巧直接應(yīng)用到SCSCLP和SCSCSP的線性規(guī)劃松弛的對偶規(guī)劃上,并不能在多項(xiàng)式時間內(nèi)控制對偶上升過程.為了克服這一困難,我們將對偶規(guī)劃進(jìn)行了松弛,分別設(shè)計并分析了SCSCLP的原始對偶η-近似算法和SCSCSP的原始對偶2η-近似算法.其中,叼為元素在子集族中出現(xiàn)的頻率的最大值.在帶線性懲罰的魯棒設(shè)施選址問題(RFLPLP)中,同時考慮了異常值和懲罰性,允許一些顧客的需求不被滿足.具體來講,RFLPLP中異常值的個數(shù)是給定的,且每個顧客都對應(yīng)一定的線性懲罰費(fèi)用.目標(biāo)是選擇一個開設(shè)的設(shè)施集合,將一部分顧客連接到開設(shè)的設(shè)施,排除異常值顧客,懲罰剩下的顧客,最終使得設(shè)施開設(shè)費(fèi)用,顧客與設(shè)施之間的連接費(fèi)用以及顧客的懲罰費(fèi)用之和最小.給出了問題的數(shù)學(xué)規(guī)劃模型.針對該問題的特殊結(jié)構(gòu),設(shè)計了原始對偶近似算法,分析得到的近似比為3；之后結(jié)合貪婪增廣技巧,設(shè)計并分析了改進(jìn)的算法,將近似比3改進(jìn)到2.在帶次模懲罰的優(yōu)先設(shè)施選址問題(PFLPSP)中,同時考慮了優(yōu)先性和次模懲罰性.具體來講,PFLPSP中每個顧客都有一定的服務(wù)水平要求,并且每個設(shè)施的開設(shè)費(fèi)用是關(guān)于服務(wù)水平的遞增函數(shù),與顧客相連接的設(shè)施必須是開設(shè)的且能夠滿足顧客的服務(wù)水平要求；顧客的每個子集都對應(yīng)一定的次模懲罰費(fèi)用.目標(biāo)是選擇一個開設(shè)的設(shè)施集合,且選擇被懲罰的顧客集合,將未被懲罰的顧客連接到能夠滿足其服務(wù)水平要求的開設(shè)設(shè)施上,最終使得設(shè)施開設(shè)費(fèi)用,顧客與設(shè)施之間的連接費(fèi)用以及顧客的懲罰費(fèi)用之和最小.給出了問題的數(shù)學(xué)規(guī)劃模型.結(jié)合問題的優(yōu)先性和次模懲罰性,設(shè)計了原始對偶近似算法,并對算法得到的解進(jìn)行了分析,得到的近似比為3；之后結(jié)合貪婪增廣技巧,設(shè)計并分析了改進(jìn)的算法,將近似比3改進(jìn)到了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..
【學(xué)位授予單位】：北京工業(yè)大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2016
【分類號】：O224

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 周兵;關(guān)于圖的面服務(wù)型選址問題[J];上海機(jī)械學(xué)院學(xué)報;1982年03期

2 馬云峰;楊超;張敏;郝春艷;;基于時間滿意的最大覆蓋選址問題[J];中國管理科學(xué);2006年02期

3 劉文博;;固定容量設(shè)備選址問題的求解算法研究[J];遼寧省交通高等�？茖W(xué)校學(xué)報;2006年04期

4 代文強(qiáng);徐寅峰;何國良;;占線中心選址問題及其競爭算法分析[J];系統(tǒng)工程理論與實(shí)踐;2007年10期

5 胡丹丹;楊超;;在競爭環(huán)境中的擁塞設(shè)施截流選址問題[J];系統(tǒng)工程理論與實(shí)踐;2010年01期

6 陳開周;王效俐;;選址問題的新研究[J];系統(tǒng)工程;1990年01期

7 劉汝臣;選址問題研究[J];沈陽工程學(xué)院學(xué)報(自然科學(xué)版);2005年04期

8 華國偉;楊豐梅;黎建強(qiáng);;兩個雙目標(biāo)競爭選址問題模型[J];系統(tǒng)工程理論與實(shí)踐;2007年01期

9 馬云峰;劉勇;楊超;;一類帶時間和容量約束的截流選址問題[J];武漢科技大學(xué)學(xué)報(自然科學(xué)版);2007年02期

10 譚素平;易斌;;設(shè)施選址問題綜述[J];科技信息;2012年22期

相關(guān)會議論文 前8條

1 趙一新;;淺談博物館的選址問題[A];浙江省博物館學(xué)會2001年學(xué)術(shù)研討會文集[C];2001年

2 王文峰;郭波;劉新亮;;多級覆蓋設(shè)施選址問題建模及求解方法研究[A];第九屆中國管理科學(xué)學(xué)術(shù)年會論文集[C];2007年

3 張敏;楊s，

本文編號：2039684