設(shè)施選址與K-中間點(diǎn)問題的復(fù)雜性與近似算法.pdf

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

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

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

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

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

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

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

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

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

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

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

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

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