摘要
下模函数的最值问题在组合优化问题中有着广泛的应用,本文给出了具有均匀拟阵约束下下模函数最大值问题的贪婪近似算法,并讨论了所给算法的性能保证.
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.
基金
国家自然科学基金资助项目(60871027)
陕西省科技计划项目(2011JM8031)
关键词
组合优化问题
下模函数
近似算法
性能保证
combinatorial optimization problem
submodular function
approximation algo-rithm
performance guarantee
