摘要
对双背包约束条件下下模函数最大值问题用近似算法求解,其性能保证为1-e-1,该算法的时间复杂性为ο(n5).
In this paper, we obtain an （1 -e-1）-approximation alforithm for maximizing a nondecreasing submodular set function subject to double/knapsack constraint. This algorithm requireso（ n5）time complexity.
出处
《洛阳理工学院学报（自然科学版）》
2009年第3期56-59,共4页
Journal of Luoyang Institute of Science and Technology：Natural Science Edition
关键词
下模函数
近似算法
性能保证
Submodular function
Approximation algorithm
Performance guarantee
