求解具有均匀拟阵约束下下模函数的最大值问题的贪婪算法及其性能保证
The Greedy Algorithm and Its Performance Guarantees for Maximizing Submodular Function Subject to a Even Matroid
梁国宏 1王武民1
作者信息
- 1. 空军工程大学理学院数理系,陕西西安710051
- 折叠
摘要
下模函数的最值问题在组合优化问题中有着广泛的应用,本文给出了具有均匀拟阵约束下下模函数最大值问题的贪婪近似算法,并讨论了所给算法的性能保证.
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.
关键词
组合优化问题/下模函数/近似算法/性能保证Key words
combinatorial optimization problem/submodular function/approximation algo-rithm/performance guarantee引用本文复制引用
基金项目
国家自然科学基金(60871027)
陕西省科技计划项目(2011JM8031)
出版年
2011
NETL
NSTL
维普
万方数据