求解下模集函数最大值问题的局部搜索算法  

Local Search Algorithm for Solving Maximizing Submodular Set Function

作　　者：王武民[1] 张防防[1] 柘晓莉[1] 何尚录[1] 

机构地区：[1]兰州交通大学数理与软件工程学院,甘肃兰州730070

出　　处：《温州大学学报（自然科学版）》2008年第3期12-17,共6页Journal of Wenzhou University(Natural Science Edition)

摘　　要：给出了求解具有简单约束的下模集函数最大值问题的一种局部搜索算法,并讨论了所给算法的性能保证.该算法的基本思想是:算法每次迭代总是在当前近似解集的邻域内,求出使目标函数取得最大的集合,将其作为新的近似解集.分析表明,所给算法是一种多项式时间近似算法.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.

关 键 词：组合优化 下模集函数 近似算法 性能保证 

分 类 号：O224[理学—运筹学与控制论]