| 求解具有均匀拟阵约束下下模函数的最大值问题的贪婪算法及其性能保证 |
| |
| 引用本文： | 梁国宏,王武民.求解具有均匀拟阵约束下下模函数的最大值问题的贪婪算法及其性能保证[J].青海师专学报,2011(5):25-27. |
| |
| 作者姓名： | 梁国宏 王武民 |
| |
| 作者单位： | 空军工程大学理学院数理系,陕西西安710051 |
| |
| 基金项目： | 国家自然科学基金资助项目（60871027）; 陕西省科技计划项目（2011JM8031） |
| |
| 摘 要： | 下模函数的最值问题在组合优化问题中有着广泛的应用,本文给出了具有均匀拟阵约束下下模函数最大值问题的贪婪近似算法,并讨论了所给算法的性能保证.
|
| 关 键 词： | 组合优化问题 下模函数 近似算法 性能保证 |
The Greedy Algorithm and Its Performance Guarantees for Maximizing Submodular Function Subject to a Even Matroid |
| |
| LIANG Guo-hong,WANG Wu-min.The Greedy Algorithm and Its Performance Guarantees for Maximizing Submodular Function Subject to a Even Matroid[J].Journal of Qinghai Junior Teachers' College,2011(5):25-27. |
| |
| Authors: | LIANG Guo-hong WANG Wu-min |
| |
| Institution: | (Department of Mathematics and Physics,Air Force Engineering University,Xi＇an Shanxi 710051,China) |
| |
| Abstract: | Maximizing submodular function has widely used in combinatorial optimization problem,in this paper,we present an greedy algorithm of maximizing submodular function subject to an maximizing submodular function subject to a even matroid,and discuss its performance guarantee. |
| |
| Keywords: | combinatorial optimization problem submodular function approximation algo-rithm performance guarantee |
| 本文献已被 维普 等数据库收录！ |
