擬陣交構(gòu)約束的下模函數(shù)最大值問題的近似算法及其分析＊

張立群

（蘭州交通大學 數(shù)理與軟件工程學院，甘肅 蘭州 730070）

0 引言

組合優(yōu)化問題是在給定的有限集所具備的某些條件的子集中，按某種目標找出一個最優(yōu)符合標準的一類數(shù)學規(guī)劃問題［1］.所研究的問題涉及電路設(shè)計問題、運輸線路問題、裝箱問題［2］等很多領(lǐng)域.下模函數(shù)是一類定義在有限的冪集上或格上的相對比較特殊的實值函數(shù)，下模函數(shù)的最值研究在組合優(yōu)化中起著重要的作用.

下模函數(shù)定義如下：給定一個有限集E和定義在E上的冪集合2E上的一個函數(shù)f：2E→Z，這里2E是由E的所有2｜E｜個子集組成的集合，如果對于E中任意兩個集合A和B，都滿足不等式

f（A）＋f（B）≥f（A∩B）＋f（A∪B），則稱f（·）是一個下模函數(shù).

本文考慮求解m個擬陣交構(gòu)成的獨立系統(tǒng)約束下的下模函數(shù)的最大值問題，即

OPT＝ max｛f（S），S∈F｝，

其中（E，F(xiàn)）是由m個擬陣的交構(gòu)成的獨立系統(tǒng).

1 若干定義、引理及其證明

定義1 設(shè)E是一個有限集合，L是E的一個子集族，若滿足I∈L且I′?I，則I′∈L，稱L中子集為獨立子集，稱（E，L）是一個獨立系統(tǒng).

定義2 設(shè)E是一個有限集合，L是一族E的子集合.如果（E，L）滿足兩個條件：

（1）若I∈L且I′?I，則I′∈L；

（2）對于E中的任意一個子集F，有u（F）＝v（F）；

就稱其是一個擬陣.

給定E的一個子集F，若F的任意一個獨立子集都不嚴格包含子集I?F，則稱I是F的一個極大獨立子集.對任意集合I?E，令｜I｜表示I中所包含元素的個數(shù).定義：

u（F）≡min｛｜I｜，I是F的一個極大獨立子集｝，v（F）≡max｛｜I｜，I是F的一個獨立子集｝.

證明 考慮以下給出的線性規(guī)劃：

容易得到其對偶規(guī)劃為

由于ρi≥ρi＋1，Zi＝ρi－ρi＋1，i＝1，2，…，k－1，ρk＝0是對偶可行解，其最優(yōu)值為，由線性規(guī)劃的對偶定理，易說明引理成立.

2 給出近似算法及其性能保證

OPT＝max｛f（S），S∈F｝，其中（E，F(xiàn)）是由m個擬陣的交構(gòu)成的獨立系統(tǒng).

給出近似算法及其近似度分析，求解fS｜F的近似算法示意［5］如下：

第1步 令i＝1，S0＝?，E0＝E；

第2步 若Ei－1＝?，則停止計算；

第3步 求ei∈Ei－1，使其滿足α·ρeij（Si－1）≥maxe∈Ei－1ρe（Si－1），α＞0；

第4步 判斷Si－1∪ ｛ei｝是否屬于F；

第5步 若Si－1∪ ｛ei｝不屬于F，則令Ei－1＝Ei－1＼｛ei｝，返回第2步；

若Si－1∪ ｛ei｝∈F，則令Si＝Si－1∪ ｛ei｝，ρi－1＝ρei（Si－1），Ei＝Ei－1＼｛ei｝；

第6步 令i＝i＋1，返回第2步.

下面繼續(xù)給出用近似算法求出的近似解的近似度分析.

定理 設(shè)（E，F(xiàn)）是一個由m個擬陣的交集相對獨立地構(gòu)成的系統(tǒng)，f是定義在Ω上的非負非減下模函數(shù)［4］.如果將Zg與OPT分別記作是通過以上近似算法得到的目標函數(shù)值和目標函數(shù)最優(yōu)解，那么有

證明 設(shè)S和T分別是問題fS｜F近似算法的解和最優(yōu)解，｜S｜＜k，由于（E，F(xiàn)）是一個獨立的系統(tǒng)，并不一定是擬陣，因此｜T｜不一定是k.

對于t＝1，2，…，k，令St－1＝T∩ （Ut＼Ut－1） ，Ut是第t次迭代得到的解集.為不失一般性，設(shè)U0＝ ?，Uk＝E，ρ＊（Si）＝ maxe∈Eiρe（Si），i＝1，2，…，k－1.

由于f是非負非減的下模函數(shù)，由引理2可以得到如下關(guān)系：

設(shè)t∈ ｛1，2，3，…，k｝，ρq（t）＝min｛ρi｜i＝1，2，…，t－1｝.對任意e∈T∩ （Ut＼Ut－1），由于f具有下模性，所以有

由ρ＊的定義和算法可得：ρe（S）≤ρe（St）≤ρ＊（St）≤ρ＊（Sq）（t）＋1）≤αρq（t）.

令ρ′t－1＝αρq（t），則有

由于q（t）具有非增性，所以ρ′t－1也具有非增性，即ρ′t－1≥ρ′t.另一方面

由上述不等式（1）和（2）可得

注意到St－1∈T∩ （Ut＼Ut－1） ，則有＝T∩Ut.

由于T是擬陣的獨立集，rM（SPM（St））＝t，，于是有

因為對 ?t，ρ′t，St≥0，ρ′t具有非增性，在引理2中，令，由上述不等式（5）有

再由不等式（4）得

即

［1］ 陳寶林.最優(yōu)化理論與算法［M］.北京：清華大學出版社，2006.

［2］ 羅亮，賈欣鑫，何尚錄，等.求解組合拍賣問題最大值的貪婪算法［J］.黑龍江科技學院學報，2008，18（5）：382－384.

［3］ FISHER M L，NEMHAUSER G L，WOLSEY L A，et al.An analysis of approximations for maximizing submodular set functions－II［J］.Mathematical Programming Study，1978，8：73－87.

［4］ SVIRIDENKO M.A note on maximizing a submodular set function subject to knapsack constraint［J］.Operations Research Letters，2004，32：41－43.

［5］ 王武民，張防防，柘曉莉，等.求解下模集函數(shù)最大值問題的局部搜索算法［J］.溫州大學學報：自然科學版，2008，29（3）：12－17.