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

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

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

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

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

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

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

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

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