求解具有均匀拟阵约束下下模函数的最大值问题的贪婪算法及其性能保证  

The Greedy Algorithm and Its Performance Guarantees for Maximizing Submodular Function Subject to a Even Matroid

作　　者：梁国宏[1] 王武民[1] 

机构地区：[1]空军工程大学理学院数理系,陕西西安710051

出　　处：《青海民族大学学报（教育科学版）》2011年第5期25-27,共3页Journal of Qinghai Junior Teachers' College

基　　金：国家自然科学基金资助项目(60871027);陕西省科技计划项目(2011JM8031)

摘　　要：下模函数的最值问题在组合优化问题中有着广泛的应用,本文给出了具有均匀拟阵约束下下模函数最大值问题的贪婪近似算法,并讨论了所给算法的性能保证.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.

关 键 词：组合优化问题 下模函数 近似算法 性能保证 

分 类 号：O221[理学—运筹学与控制论]