| 求解多背包约束下下模集函数最大值的近似算法及其性能保证 |
| |
| 引用本文： | 李小平,赵杏利,雷习军,何尚录.求解多背包约束下下模集函数最大值的近似算法及其性能保证[J].温州大学学报(自然科学版),2010,31(1):6-10. |
| |
| 作者姓名： | 李小平 赵杏利 雷习军 何尚录 |
| |
| 作者单位： | 兰州交通大学数理与软件工程学院,甘肃兰州,730070 |
| |
| 摘 要： | 将部分穷举法与贪婪算法相结合，给出求解多背包约束下非减下模集函数最大值的近似算法．证明了该算法的性能保证是1-e^-1，算法的时间复杂性为O（3n^4）．
|
| 关 键 词： | 下模集函数 贪婪算法 性能保证 背包约束 |
Approximation Algorithm for Maximum of Submodular Set Function Subject to Multi-constraint Knapsack and Its Performance Guarantee |
| |
| LI Xiaoping,ZHAO Xingli,LEI Xijun,HE Shanglu.Approximation Algorithm for Maximum of Submodular Set Function Subject to Multi-constraint Knapsack and Its Performance Guarantee[J].Journal of Wenzhou University Natural Science,2010,31(1):6-10. |
| |
| Authors: | LI Xiaoping ZHAO Xingli LEI Xijun HE Shanglu |
| |
| Institution: | LI Xiaoping,ZHAO Xingli,LEI Xijun,HE Shanglu (School of Mathematics,Physics , Software Engineering,Lanzhou Jiaotong University,Lanzhou,China 730070) |
| |
| Abstract: | |
| |
| Keywords: | Submodular Set Function Greedy Algorithm Performance Guarantee Knapsack Constraint |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
