| 求解下模集函数最大值问题的局部搜索算法 |
| |
| 引用本文： | 王武民,张防防,柘晓莉,何尚录.求解下模集函数最大值问题的局部搜索算法[J].温州大学学报(社会科学版),2008(3):12-17. |
| |
| 作者姓名： | 王武民 张防防 柘晓莉 何尚录 |
| |
| 作者单位： | 兰州交通大学数理与软件工程学院,甘肃兰州730070 |
| |
| 摘 要： | 给出了求解具有简单约束的下模集函数最大值问题的一种局部搜索算法，并讨论了所给算法的性能保证．该算法的基本思想是：算法每次迭代总是在当前近似解集的邻域内，求出使目标函数取得最大的集合，将其作为新的近似解集．分析表明，所给算法是一种多项式时间近似算法．
|
| 关 键 词： | 组合优化 下模集函数 近似算法 性能保证 |
Local Search Algorithm for Solving Maximizing Submodular Set Function |
| |
| WANG Wumin,ZHANG Fangfang,ZHE Xiaoli,HE Shanglu.Local Search Algorithm for Solving Maximizing Submodular Set Function[J].Journal of Wenzhou University Natural Science,2008(3):12-17. |
| |
| Authors: | WANG Wumin ZHANG Fangfang ZHE Xiaoli HE Shanglu |
| |
| Institution: | (School of Mathematics, Physics and Software Engineering, Lanzhou Jiaotong University, Lanzhou, China 730070) |
| |
| Abstract: | 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. |
| |
| Keywords: | Optimal combination Submodular set function Approximation algorithm Performance guarantee |
| 本文献已被 维普 等数据库收录！ |
