多维背包约束下单调非减下模函数最大值的贪婪算法

宫兴荣，何尚录，杨留猛

(兰州交通大学 数理与软件工程学院，兰州 730070)

则称f 是定义在Ω 上的下模集函数. 又若对∀X，Y∈Ω 且X⊆Y，f(X)≤f(Y)，则称f 是单调非减的。

考虑如下组合最优化问题:

其中B，C，ci，di(i∈I))是非负整数，f(X)是非负非减的下模集函数。

上述问题属于NP-难问题，没有十分有效的求解方法，特别是多项式时间算法，于是人们主要研究求解此类问题的比较有效的近似算法。在求解组合最优化问题的各种近似算法中，贪婪算法是最简单且最为有效的算法.Nemhauseretal 考虑了单背包约束下ci=1(i∈I)的特殊情形，给出了一种简单贪婪算法并证明了性能保证为1 - e-1。M.Suiridenko结合部分穷举法与贪婪算法，给出了一般情形下单背包约束问题的一种改进的贪婪算法，并证明了其性能保证为1 -e-1。在此将这种情况中的思想推广到多维背包约束的情形，给出求解问题(1)的贪婪算法，并证明了所给算法的性能保证为1 -e-1。所谓性能保证是指若由近似算法所求近似解至少是精确解的∂倍，则称此近似算法的性能保证为∂。文中给出若干引理及其证明、问题(1)的近似算法，并证明了其性能保证。

1 若干引理及证明

引理2 单调非减的集函数f(X)是Ω 上的下模集函数当且仅当

由f 是单调非减的下模集函数及引理1，得

(充分性)设函数f 满足不等式

得到:

即对∀Α⊆Β⊆I，i∈IΒ，有

所以f 是Ω 上的非减的下模集函数。

引理3 设P，D 是任意正整数，ρi( 1，2，…，p )是任意非负实数，则有以下不等式

又由式(2)得

考虑如下线性规划

求得该线性规划的可行解:

上述线性规划的对偶规划:

求得该对偶规划的可行解:

不难看出这两个线性规划的最优解相等，即有

2 算法及其分析

2.1 基本思想

列举出基数为1 或2 的所有可行解，找出使目标函数值取最大值的可行解(最优解集)，用X1表示;考虑基数为3 的所有可行解，在保证当前可行解集在多背包约束下可行的情况下，找出使目标函数取最大值的集合，用X2表示;若f则输出X1，否则输出X2。

2.2 具体算法

(3)找出

(4)若ItXt=∅，终止，否则令t=t+1，转(3);

(5)求出所有的由U 开始的Xt，并计算f(Xt)，

2.3 算法的时间复杂性

由于基数不超过3 的子集个数最多有3n3，故算法最多循环3n3次，而每次循环需调用一次贪婪算法求解，其复杂度为Ο(n)，故其算法的时间复杂度为Ο(n4)。

2.4 算法的性能保证

定理1:求解问题(1)的上述贪婪算法的性能保证是1-e-1。

证明:定义函数g(X)=f(X)-f(Y)，因f(X)是非减下模函数，故对∀X 满足Y⊆X⊆I，g(X)都是非减下模函数。因此g(X)满足引理2 中的不等式(2)。

设t*+1 是算法中的不能将it*+1∈X*增加到Xt*中的第一步，则:Xt*+1=Xt*，It*+1=It* {it*+1} ，设t*+1 是从第t 步开始不能增加到Xt中的第一步，则:Xt= Xt-1，It=若

令Xt，t=1，2，…t*，是算法在第t 次迭代后所得的近似解。

根据不等式(2)及g(X)的定义有:

对t=1，2，…t*均成立。

根据等式:

和不等(3)，(5)得:

故即证得上述算法的性能保证为1 -e-1。

［1］ILEV V R. An approximation guarantee of the greedy descent algorithm for minimizing a submodular set function［J］.Discrete Applied M athematics，2001，114:131-146.

［2］SVIRIDENKO M.A note on maximi zing a submodular set function subject to a knapsack constraint［J］.OperationsResearch Letters，2004，32(2):41-43.

［3］罗亮，贾欣鑫，何尚录.求解组合拍卖问题最大值的贪婪算法［J］.黑龙江科技学院学报，2008，18(5);382-384.

［4］雷习军，赵杏利，李小平，等.求解背包约束下下模函数最大值问题的近似算法及其性能保证［J］.淮阴工学院学报，2010，19(3):15-18.

［5］李小平，赵杏利，雷习军，等.求解下模福利问题的一种随机算法及其性能保证［J］.兰州交通大学学报，2011，30(1):139-141.