關(guān)于一些網(wǎng)絡(luò)最優(yōu)化問題的近似算法的研究.pdf

1、隨著網(wǎng)絡(luò)和網(wǎng)絡(luò)技術(shù)的高速發(fā)展，很多網(wǎng)絡(luò)上的最優(yōu)化問題被提出.不幸的是，很多這些問題都被證明是NP-完備問題.這就意味著，目前這些問題不可能在多項(xiàng)式時(shí)間內(nèi)得到最優(yōu)解.因此，研究者們就致力于尋找這些NP-完備問題的近似算法.
　　 本文主要研究了斯坦納樹問題和連通控制集問題及它們變形的近似算法.這些問題都是網(wǎng)絡(luò)中經(jīng)典的最優(yōu)化問題，同時(shí)也是經(jīng)典的NP-完備問題.特別地，在單位圓盤圖上，這些問題依然是NP-完備的.對(duì)于這些問題，我們都給

2、出了近似算法，并對(duì)算法進(jìn)行了理論分析，給出了算法的近似比.
　　 本文共分為三章.第一章首先介紹了圖論中的一些基本概念和記號(hào).然后，介紹了計(jì)算復(fù)雜度理論的一些基本概念.接下來，我們給出了近似算法的基本概念，并通過頂點(diǎn)覆蓋問題和它的一個(gè)的近似算法為例，對(duì)其巾的一些概念進(jìn)行了解釋.最后，羅列了本文得到的主要結(jié)論.
　　 第二章主要研究了斯坦納樹問題變形的近似算法.給定一個(gè)邊賦權(quán)圖G=(V,E)和邊權(quán)函數(shù)c，及terminal

3、集X(∪-)V，斯坦納樹問題的目標(biāo)是尋找一棵權(quán)重最小且連接terminal集巾所有頂點(diǎn)的樹.斯坦納樹問題是一個(gè)經(jīng)典的最優(yōu)化問題和NP-完備問題.在本章的開始，我們將介紹斯坦納樹問題并綜述其研究進(jìn)展.
　　 在第二章的第二節(jié)，我們研究了一個(gè)斯坦納樹問題的變形，selected-internal斯坦納樹問題.給定一個(gè)邊賦權(quán)完全圖G=(V,E)和邊權(quán)函數(shù)c，及兩個(gè)子集x'(∪-) X(∪-)V滿足｜x-x'｜≥2，selected-i

4、nternal斯坦納樹問題是在圖G中尋找一棵最小的子樹T連接X中的所有頂點(diǎn)，并且X'巾的所有頂點(diǎn)均不是T的葉子節(jié)點(diǎn).假設(shè)c是度量函數(shù)，本節(jié)得到了此問題的一個(gè)近似比為(1+ρ)的近似算法，在這里ρ是目前為止斯坦納樹問題最好的近似比.
　　 對(duì)于給定的一個(gè)頂點(diǎn)賦權(quán)圖G=(V,E)和頂點(diǎn)賦權(quán)函數(shù)ω，及terminal集X(∪-)V，頂點(diǎn)賦權(quán)斯坦納樹問題的目標(biāo)是尋找一棵總權(quán)重最小且連接所有terminal集中頂點(diǎn)的樹.我們將在第二章余下

5、的內(nèi)容中在單位圓盤圖上研究這個(gè)問題.在第二章的第三節(jié)，首先利用支撐樹方法，本文得到了一個(gè)近似比為5的近似算法.然后，通過將權(quán)重從頂點(diǎn)轉(zhuǎn)移到邊，給出了一個(gè)近似比為2.5ρ的近似算法.最后，假設(shè)terminal集是c-local的，我們證明了單位圓盤圖上的頂點(diǎn)賦權(quán)斯坦納樹問題存在多項(xiàng)式時(shí)間的近似模式.也就是說，對(duì)于任意的ε＞0，總存在一個(gè)近似算法滿足其近似比為l+ε.
　　 第三章將研究單位圓盤圖上的連通控制集問題及其變形.給定圖G

6、=(V,E)，稱頂點(diǎn)子集C(∪-)V是一個(gè)連通控制集，如果：1)對(duì)于任意的頂點(diǎn)υ∈V-C，υ總存在鄰點(diǎn)在C中;2)導(dǎo)出子圖G[C]是連通的.連通控制集問題的目標(biāo)是尋找圖G中一個(gè)包含頂點(diǎn)個(gè)數(shù)最少的連通控制集.第三章的第一節(jié)首先介紹了這個(gè)問題的背景及研究進(jìn)展.然后，給出了計(jì)算連通控制集的基本思路.
　　 第三章的第二節(jié)考查了極大獨(dú)立集(MIS)與最小連通控制集的關(guān)系.由于每個(gè)MIS都是控制集且可在多項(xiàng)式時(shí)間內(nèi)得到，因此研究者們經(jīng)常通

7、過尋找MIS并連接它們來得到一個(gè)連通控制集.所以，MIS的大小與最小連通控制集大小之間的比值就在近似比分析中起著關(guān)鍵的作用.在本節(jié)中，借助于Voronoi圖和歐拉公式，我們改進(jìn)了這個(gè)比值，從而也就改進(jìn)了所有基于這種方法的近似算法的近似比.
　　 第三章的第三節(jié)研究了單位圓盤圖上的d-hop連通控制集.首先，對(duì)于一種特殊情況，2-hop連通控制集(TCDS或2-CDS)，我們提出了一個(gè)分布式的算法.然后，證明了算法輸出結(jié)果的大小不

8、會(huì)超過17.421opt+51.456，這里opt表示2-CDS問題最優(yōu)解的大小.最后，對(duì)于任意的整數(shù)d，通過推廣TCDS算法，使其成為了一個(gè)d-CDS的常數(shù)近似比的近似算法.
　　 第三章的第四節(jié)研究了賦權(quán)連通控制集問題，一個(gè)連通控制集問題的變形.利用已有的結(jié)論并結(jié)合頂點(diǎn)賦權(quán)斯坦納樹問題的PTAS算法，本文得到了單位圓盤圖上此問題的一個(gè)近似比為5+ε的近似算法.接下來，我們將研究的方向從二維平面擴(kuò)展劍三維空間，即研究單位圓球圖