宫兴荣，何尚录，杨留猛

(兰州交通大学 数理与软件工程学院，兰州 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)得

考虑如下线性规划

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

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

求得该对……