設施選址與K-中間點問題的復雜性與近似算法.pdf

1、回顧四十多年的研究歷史發(fā)現(xiàn)，度量距離空間(Metric)中的兩問題近似算法研究是人們關注的焦點，即問題中設施與客戶之間連接費用滿足三角不等式。然而，現(xiàn)實世界里，兩問題的很多應用模型中連接費用并不一定滿足上述約束條件，我們稱它們?yōu)橐话憔嚯x空間(或非度量空間)中的UFL和k-median 問題?；萜展九c英國電信合作研究的通信網(wǎng)絡中的動態(tài)路由算法就曾經(jīng)涉及此類問題。 相比度量距離空間中的UFL和k-median問題研究成果，一般距離

2、空間中的兩問題算法研究工作多年來非常少見。因此，本文主要圍繞這類UFL和k-median 問題，研究它們的復雜性，設計分析它們的近似算法，給出如下研究成果。 (1)我們首先提出了一類一般距離空間中的UFL問題，簡稱～般UFL問題，即給定問題中客戶與設施之間最大連接費用至多是最小連接費用的ω倍，表示為d<,max>/d<,min>≤ω。在NP￠DTIME(n<'O(loglogn)>)的假設下，將集合覆蓋問題歸約到一般UFL問題，

3、利用前者的不可近似性結論，證明滿足d<,nax>/d<,min>≤ω+ε的UFL 問題不存在近似性能比小于1.243+0.3161n(ω-1)的多項式時間算法，進而推出，一般UFL問題亦不存在任意常數(shù)近似算法；設近似解中設施費用、連接費用與最優(yōu)解中設施費用、連接費用之比分別為r<,f>和r<,c>，證明上述UFL問題不存在多項式時間近似算法使得r<,c><1+(ω-1)·e<'r<,f>>。 自1999年Guha等人<'[30]

4、>給出了度量距離空間中的UFL問題算法1.463的不可近似性證明后，一般距離空間中的UFL問題，人們一直渴望見到有關其復雜性的分析報道，但近年來始終未見相關結果出現(xiàn)。 我們恰好找到一類特殊的UFL問題，借助它首次嚴格證明了一般UFL問題算法的不可近似性結果。 (2)設計了一般UFL問題局部搜索算法，證明求解d<,max/d<,min>≤ω的UFL問題，算法所得解滿足如下關系，L<,f>+2L<,c>≤O<,f>+(1+

5、ω)·D<,c>，其中L<,f>,L<,c>，O<,f>O<,c>分別為局部最優(yōu)解與全局最優(yōu)解中的設施費用和連接費用：進而推出，存在1≤α≤2，保證局部搜索算法的近似度為(1+ω)/α。隨后，利用實驗進一步研究了算法的實際計算效果，統(tǒng)計結果發(fā)現(xiàn)，參與實驗的所有實例實際求解結果的平均近似度小于1.001；進一步分析實驗結果，我們又提出了算法的改進方法。 1982年Hochbaum<'[27]>首次研究了一般距離空間中的UFL問題，

6、并設計了平均近似度D(10gm)的多項式時間算法，其中m是問題中設施集合中的元素數(shù)；2003年Hajiiaghayi等人<'[47]>證明一般距離空間中UFL問題依舊屬于NP-hard難解問題，并設計了近似度1nm的多項式時間算法。此后一直未見有關這類UFL問題的近似算法研究結果，相比上述一般距離空間中的UFL問題算法，我們的算法在最壞情況下的近似度不隨問題實例的規(guī)模發(fā)生變化。 (3)基于給出的一般UFL問題模型，利用其分析方法

7、，建立并分析了一類一般距離空間中的k-median問題，簡稱一般k-median問題。在NP DTIME(n<'O(loglogn)>)的假設下，將集合覆蓋問題歸約到一般k-median問題，證明d<,max/d<,min>≤ω的k-mddian問題不存在近似性能比小于1+ω-1/e的多項式時間算法，進而推出，一般k-median問題亦不存在任意常數(shù)近似算法；進一步研究證明，度量距離空間中的k-median問題不存在近似性能比小于1+2

8、/e的多項式時間算法，除非NP DTTME(n<'o(loglogn)>)。 關于連接費用任意取值的K-median問題，1992年Lin和Vitter<'[29]>曾經(jīng)猜測其求解難度同集合覆蓋問題一樣，并提出證據(jù)說它的不可近似性結果極有可能通過對集合覆蓋問題歸約得出，但他們始終沒有給出嚴格證明。1999年Guha與Khuller<'[30]>曾證明不存在求解度量距離空間中的UFL問題近似性能比小于1.463的多項式時間算法，然

9、而，令人遺憾的是，與它關系最為密切的度量距離空間中的K-median問題不可近似性結果，在本文之前卻始終未見相關報道。我們有關后K-median問題的復雜性分析填補了多年來這一問題不可近似性理論研究的空白，同時也驗證了Lin和Vitter<'[29]>猜想的正確性。 (4)給出K-median問題局部搜索算法新的分析方法，證明使用最簡單的交換操作，算法求解d<,max>/d<,min>≤ω的一般K-median問題時近似度不超

10、過時間復雜度O(n)。該結果的出乎意料之處在于算法所能達到的近似度與反面結果形式十分相似；進而推出，對于度量距離空間中的K-median問題，在ω<5時局部搜索算法的近似度不超過3。我們利用仿真實驗研究了K和ω不同取值對算法求解質(zhì)量的影響，并提出了算法的改進方法。 1992年Lin和Vitter<'[29]>率先設計了一般距離空間中的k-median問題多項式時間近似算法，對于任意ε>0，算法選取(1+1/ε)(lnn+1)k個

11、設施，保證最終解的解值至多是最優(yōu)解的(1+ε)倍，此后再也未見有關一般K-median問題的算法研究結果。度量距離空間中的K-median問題，2001年Arya等人<'[41]>給出的近似度3+ε局部搜索算法仍是目前最好的結果，但其分析方法對于一般K-median問題已不適用。針對ω≤5的度量距離空間中的k-median問題，本文算法求解它時近似度保證小于3，好于現(xiàn)有3+ε的結果。 以上兩結果進～步表明，度量距離空間中的K-m

12、edian問題限制ω<5的子問題也不存在近似度小于1+2/e的多項式時間算法，但本文所給局部搜索算法可以保證求解該類子問題的近似度不超過3。尋找度量距離空間中的K-median問題近似度不超過3的多項式時間算法一直是眾多研究者關注的焦點，但近年來未見任何進展，我們恰好找到它的一類子問題，存在近似度不超過3的多項式近似算法。 (5)借鑒集合覆蓋問題算法中的思想，設計實現(xiàn)了K-median問題時間復雜度D(nmk)的新貪心算法，其中

13、n和m分別為給定問題中設施集合和客戶集合中的元素數(shù)。算法的實際計算效果在隨后基于ORLIB<'[83]>，SLLIB<'[84]>，GRLIB<'[85]>和TSPLIB<'[86]>測試集的仿真實驗中得到了驗證。尋求實用有效的k-median問題算法，滿足類似QoS路由選擇問題的需求，一直是人們的一項重要研究工作。利用Jain和vazirani<'[33]>的UFL問題算法，Jariyakul<'[55]>曾試圖設計k-median問