樹上具有懲罰費(fèi)用的限制性node multicut問題的近似算法

楊惠娟,段江梅,楊子蘭

(1.昭通學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,云南 昭通 657000; 2.麗江文化旅游學(xué)校信息學(xué)院,云南 麗江 674199)

0 引言

multicut問題是圖論與組合優(yōu)化中非常著名的問題,它具有邊和點(diǎn)兩種形式,點(diǎn)形式的multicut問題是指:給定賦權(quán)圖G=(V,E;w)及一個(gè)終端點(diǎn)對集合H?V×V,其中w:V→R+,求G的一個(gè)頂點(diǎn)子集D,使得H中的所有頂點(diǎn)對在G-D中不連通,目標(biāo)是使得D的權(quán)重盡可能小.

限制性node multicut問題是點(diǎn)形式multicut問題的一類子問題,該問題要求所求的頂點(diǎn)子集中不允許有終端點(diǎn).GUO等[1]研究了完全圖、分裂圖、區(qū)間圖上的點(diǎn)multicut 問題,并證明了該問題限制在這三類特殊圖上時(shí)也是NP難問題.PAPADOPOULOS[2]證明了置換圖上的無限制性 node multicut問題是多項(xiàng)式可解的,且設(shè)計(jì)了時(shí)間復(fù)雜度為O(n3)的算法,其中n為圖的頂點(diǎn)數(shù).

一般的multicut問題是要求所有頂點(diǎn)對被斷開,而有些頂點(diǎn)對在斷開時(shí)可能會出現(xiàn)選取的邊的權(quán)重很大的情況,這時(shí)需要考慮拒絕斷開這些頂點(diǎn)對,同時(shí)支付部分懲罰費(fèi)用,這就將multicut問題拓展到了具有懲罰費(fèi)用問題的層面.LIU等[6]將帶線性懲罰推廣到帶次模懲罰,引入了帶次模懲罰的樹上的多割問題,并且基于原始對偶方案給出了帶次模懲罰的樹上的多割問題的一個(gè)3-近似算法.HOU等[7]研究了樹上具有懲罰費(fèi)用的k-edge multicut問題,該問題推廣了樹上邊multicut問題,并運(yùn)用線性規(guī)劃理論和拉格朗日松弛技巧設(shè)計(jì)了近似值為(4+ε)的算法,其中ε為任意固定正數(shù).侯鑫[8]研究了樹上的k-獎(jiǎng)勵(lì)收集多割問題和樹上的P獎(jiǎng)勵(lì)收集多割問題,對于樹上k-獎(jiǎng)勵(lì)收集多割問題和樹上的P獎(jiǎng)勵(lì)收集多割問題,設(shè)計(jì)了求解其近似值為(4+ε)的算法,其中ε為任意固定正數(shù).侯晨菲[9]主要研究了與次模函數(shù)有關(guān)的樹上多割問題.這些文獻(xiàn)重點(diǎn)研究了不同類型的具有懲罰費(fèi)用的邊multicut 問題,但對于圖而言,要分離圖上的頂點(diǎn),可以去掉圖上的邊,也可以去掉圖上的頂點(diǎn),而這些文獻(xiàn)對于具有懲罰費(fèi)用的點(diǎn)multicut 問題的研究較少.本文提出具有懲罰費(fèi)用的限制性node multicut問題,為了得到很好的結(jié)果,將問題限制在樹上進(jìn)行研究.

1 樹上具有懲罰費(fèi)用的限制性node multicut問題

樹上具有懲罰費(fèi)用的限制性node multicut問題是指:給定頂點(diǎn)賦權(quán)樹T=(V,E;w)及頂點(diǎn)V的k個(gè)頂點(diǎn)對構(gòu)成的集合S={{s1,t1},{s2,t2},…,{sk,tk}},其中w:V-S→R+,且S中的每個(gè)終端點(diǎn)對{si,ti}都有一個(gè)非負(fù)的懲罰費(fèi)用pi,求T的一個(gè)頂點(diǎn)子集D,使得D滿足D中不含S中的點(diǎn)且對?i∈{1,2,…,k},{si,ti}在T[V-D]中不連通,其中T[V-D]表示T的由頂點(diǎn)集V-D導(dǎo)出的子圖.目標(biāo)是使D中頂點(diǎn)的權(quán)重之和與在T[V-D]中未斷開的頂點(diǎn)對的懲罰費(fèi)用之和最小.

樹上限制性node multicut問題是指:給定頂點(diǎn)賦權(quán)的樹T=(V,E;w)及頂點(diǎn)V的k個(gè)頂點(diǎn)對構(gòu)成的集合S={{s1,t1},{s2,t2},…,{sk,tk}},其中w:V-S→R+,求T的一個(gè)頂點(diǎn)子集D,使得D滿足D中不含S中的點(diǎn)且對?i∈{1,2,…,k},{si,ti}在T[V-D]中不連通.目標(biāo)是使D中頂點(diǎn)的權(quán)重之和最小.

S中的點(diǎn)稱為終端點(diǎn),若S中的點(diǎn)對{si,ti}的懲罰費(fèi)用非常大,超過斷開此點(diǎn)對所選非終端頂點(diǎn)的權(quán)重之和,此時(shí)只能斷開S中所有點(diǎn)對,則樹上具有懲罰費(fèi)用的限制性node multicut問題化為樹上限制性node multicut問題,因此該問題作為樹上限制性node multicut問題的推廣形式是NP完備的.

下面介紹如何將樹上具有懲罰費(fèi)用的限制性node multicut問題歸約到樹上限制性node multicut問題,并利用線性規(guī)劃及對偶理論設(shè)計(jì)算法進(jìn)行求解.

任給樹上具有懲罰費(fèi)用的限制性node multicut問題的一個(gè)實(shí)例I:給定頂點(diǎn)賦權(quán)的樹T=(V,E;w)及頂點(diǎn)V的k個(gè)頂點(diǎn)對構(gòu)成的集合S={{s1,t1},{s2,t2},…,{sk,tk}},其中w:V-S→R+,且S中的每個(gè)終端點(diǎn)對{si,ti}都有一個(gè)非負(fù)懲罰費(fèi)用pi,求T的一個(gè)頂點(diǎn)子集D,使得D滿足不含S中的點(diǎn)且對?i∈{1,2,…,k},{si,ti}在T[V-D]中不連通.目標(biāo)是使D中頂點(diǎn)的權(quán)重之和與在T[V-D]未斷開的頂點(diǎn)對的懲罰費(fèi)用之和最小.

下面證明實(shí)例I與實(shí)例τ(I)的解是等價(jià)的,若D是實(shí)例I的解,在T[V-D]中未被斷開的頂點(diǎn)對要支付懲罰費(fèi)用,假設(shè)被懲罰的所有頂點(diǎn)對的下標(biāo)構(gòu)成的集合為N,即N={i|?pi∈T[V-D],si,ti∈pi, ?{si,ti}∈S},其中

與實(shí)例I的目標(biāo)函數(shù)值一致.

反之,若D′是實(shí)例τ(I)的解,即S′中所有頂點(diǎn)對在T′[V′-D′]中都不連通,令D=D′∩(V-S),D″=D′∩{t1″,t2″,…,tk″},則N={i|ti″∈D″},則D是實(shí)例I的解,下標(biāo)在N中的頂點(diǎn)對集合是在T[V-D]中未斷開的集合,此時(shí)實(shí)例I與實(shí)例τ(I)的目標(biāo)函數(shù)值一樣,因此根據(jù)上述描述任給樹上具有懲罰費(fèi)用的限制性node multicut問題的一個(gè)實(shí)例I都可以轉(zhuǎn)化成樹上限制性node multicut問題的一個(gè)實(shí)例τ(I),它們的解可以相互轉(zhuǎn)換,且目標(biāo)函數(shù)值相同.

下面介紹如何利用線性規(guī)劃的相關(guān)理論知識設(shè)計(jì)求解實(shí)例τ(I)的算法,并將算法求得的解轉(zhuǎn)化為實(shí)例I的解,并證明轉(zhuǎn)化回來的解的近似值.

2 原始-對偶算法

用0-1整數(shù)規(guī)劃來描述實(shí)例τ(I).

對V′-S′中的每一個(gè)頂點(diǎn)引入布爾變量xv,用來表示頂點(diǎn)v是否在集合D′中,若v?D′,則令xv=0,若v∈D′,則令xv=1.P′i表示在樹T′中si到t′i之間的路,因?yàn)門′是樹,因此si到t′i之間的路是唯一的,此時(shí)得到實(shí)例τ(I)的0-1整數(shù)規(guī)劃,記為IP.

因?yàn)檎麛?shù)規(guī)劃的求解是NP難的,因此對上述整數(shù)規(guī)劃進(jìn)行松弛,就得如下的線性規(guī)劃記為LP.

算法的思想:從原始線性規(guī)劃的一個(gè)不可行解?v∈V′-S′,xv=0及對偶線性規(guī)劃的一個(gè)平凡可行解fi, ?i∈{1,2,…,k}開始,在每一次迭代過程中保證對偶線性規(guī)劃的解的可行性,然后逐步調(diào)整原始線性規(guī)劃的解和對偶線性規(guī)劃的解,使得原始線性規(guī)劃的解盡可能滿足可行性,而對偶規(guī)劃的解盡可能滿足最優(yōu)性,直到調(diào)整到原始線性規(guī)劃的解滿足可行性.

算法具體步驟如下:

輸出:斷開頂點(diǎn)對所選的非終端點(diǎn)構(gòu)成的集合D′

步驟1 令fi=0, ?i∈{1,2,…,k},D′=?.

步驟2 任取T′的一個(gè)頂點(diǎn)作為根節(jié)點(diǎn),假設(shè)為v0.

步驟3 計(jì)算V′中每一個(gè)頂點(diǎn)的深度,即對?v∈V′(T′)計(jì)算頂點(diǎn)v的深度d(v),d(v)表示v到v0的唯一路上邊的數(shù)目.

步驟4 將步驟3計(jì)算得到的所有頂點(diǎn)的深度d(v)從大到小進(jìn)行排序,d(vn)≥d(vn-1)≥…≥d(v0).

輸出:fi,?i∈{1,2,…,k}及集合D′.

若v∈D′,令xv=1,否則令xv=0,于是上述算法輸出的解xv,?v∈V′-S′及fi,?i∈{1,2,…,k}分別為松弛線性規(guī)劃和對偶規(guī)劃的可行解,于是得到如下結(jié)論:

根據(jù)文獻(xiàn)[10]的性質(zhì)5得出上述原始線性規(guī)劃和對偶線性規(guī)劃的可行解,滿足的互補(bǔ)松弛條件是:

(5)

圖1 si0到的路及si到ti的路

將上述算法求得的實(shí)例τ(I)的解D′,轉(zhuǎn)化成實(shí)例I的解,轉(zhuǎn)化方式為:令D=D′∩(V-S),D″=D′∩{t1″,t2″,…,tk″},則N={i|ti″∈D″}.于是得到如下定理.

證明

(6)

(7)

(8)

(9)

定理5令OPT,O′PT分別是實(shí)例I和實(shí)例τ(I)的最優(yōu)解的值,調(diào)用原始-對偶算法求解的實(shí)例τ(I)的解轉(zhuǎn)化成實(shí)例I的解,則所得的解的近似值為2.

證明 算法求得的實(shí)例τ(I)的解為D′,轉(zhuǎn)化成實(shí)例I的解為D,N,其中,D為斷開終端點(diǎn)對所選的非終端點(diǎn)集合,N為在T-D中未斷開的頂點(diǎn)對的下標(biāo)構(gòu)成的集合,因此實(shí)例τ(I)的最優(yōu)解可以轉(zhuǎn)化成實(shí)例I的一個(gè)可行解,故O′PT≤OPT,于是,再由定理3和定理4得到:

綜上所述,D中頂點(diǎn)的權(quán)重之和與在T[V-D]未斷開的頂點(diǎn)對的懲罰費(fèi)用之和小于等于最優(yōu)解的2倍,因此這樣求得的解D,N的近似值為2.

3 結(jié)語

本文研究了樹上具有懲罰費(fèi)用的限制性node multicut 問題,將該問題轉(zhuǎn)化成樹上限制性node multicut 問題,并利用線性規(guī)劃和對偶規(guī)劃的相關(guān)理論設(shè)計(jì)了近似值為2的算法.下一步將重點(diǎn)研究更多特殊圖上的具有懲罰費(fèi)用的限制性node multicut 問題及其各種推廣問題.