摘要
给出了求解具有简单约束的下模集函数最大值问题的一种局部搜索算法,并讨论了所给算法的性能保证.该算法的基本思想是:算法每次迭代总是在当前近似解集的邻域内,求出使目标函数取得最大的集合,将其作为新的近似解集.分析表明,所给算法是一种多项式时间近似算法.
This paper presents a local search algorithm which maximizes a nondecreasing submodular set function and discusses its performance guarantee as well. The basic idea lies in which each iterative algorithm is always in the neighborhood sets of the current approximate solution, solving a set which maximize the objective function is a new approximate set. Analysis shows that the algorithm is a polynomial time algorithm.
出处
《温州大学学报（自然科学版）》
2008年第3期12-17,共6页
Journal of Wenzhou University(Natural Science Edition)
关键词
组合优化
下模集函数
近似算法
性能保证
Optimal combination
Submodular set function
Approximation algorithm
Performance guarantee
