摘要
下模集函数最大值问题属于NP-难问题,难以得到有效的求解方法。针对这一情况,运用概率分布方法,给出了求解该问题的一种近似算法,并证明算法的性能保证为1/3。组合优化问题实例证明了该算法的有效性。该研究可为求解下模集函数最大值问题提供新的思路。
Targeted at difficulties due to an effective algorithm for the problem of maximizing a submodular set function classified as NP-hards, this paper gives a new approximation algorithm for maximizing submodular set functions by means of probability distribution. The paper proves that the performance guarantee of this algorithm is 1/3. The effect of this algorithm is illustrated by using a combinatorial optimization problem. This study provides a new idea for solving maximizing submodular set function.
出处
《黑龙江科技学院学报》
CAS
2010年第5期391-394,共4页
Journal of Heilongjiang Institute of Science and Technology
关键词
下模集函数
最大值问题
近似算法
性能保证
组合优化问题
submodular set function
maximum value problem
approximation algorithm
performance guarantee
combinatorial optimization problem
