| 求解多维约束下下模函数最大值的改进贪婪算法 |
| |
| 引用本文： | 张生,何尚录.求解多维约束下下模函数最大值的改进贪婪算法[J].系统科学与数学,2009,29(4):512-518. |
| |
| 作者姓名： | 张生 何尚录 |
| |
| 作者单位： | 1. 张生,内蒙古师范大学数学科学学院,呼和浩特,010022
2. 何尚录,兰州交通大学数理与软件工程学院,兰州,730070 |
| |
| 摘 要： | 提出了多维约束下下模函数最大值问题,分析其在组合优化中的重要应用.此问题是NP-难的,故给出了求解该问题的改进贪婪算法.最后,从理论上证明了这一算法的时间复杂性和性能保证.说明该算法是多项式时间近似算法,同时也具有较好的性能保证.
|
| 关 键 词： | 组合优化 下模函数 贪婪算法 性能保证 |
| 收稿时间： | 2007-6-15 |
An Improved Greedy Algorithm for Maximizing a Submodular Set Function with Multiple Constraints |
| |
| ZHANG Sheng,HE Shanglu.An Improved Greedy Algorithm for Maximizing a Submodular Set Function with Multiple Constraints[J].Journal of Systems Science and Mathematical Sciences,2009,29(4):512-518. |
| |
| Authors: | ZHANG Sheng HE Shanglu |
| |
| Institution: | (1)College of Mathematics Science, Inner Mongolia Normal University, Huhhot010022; (2)College of Mathematics, Physics and Software Engineering, Lanzhou Jiaotong University, Lanzhou 730070. |
| |
| Abstract: | The problem of maximizing a submodular set function with multiple constraints is considered, which has important application in combinatorial optimization theory. The problem is $NP$-hard and then an improved greedy algorithm is given. The time complexity and performance analysis of the algorithm are proved, then it is shown that the algorithm is polynomial time approximate and has a relatively good performance. |
| |
| Keywords: | Combinatorial optimization submodular set function greedy algorithm performance guarantee |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《系统科学与数学》浏览原始摘要信息 |
| 点击此处可从《系统科学与数学》下载免费的PDF全文 |
|
