拟阵约束下非负非减下模函数最大值问题的近似算法及其性能保证  

The Greedy Algorithm and Its Performance Guarantees for Maximizing Nonne-ativeand Non-decreasing Submodular Function Subject to a Partition Matroid Constraint

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

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

出　　处：《德州学院学报》2012年第4期9-10,共2页Journal of Dezhou University

基　　金：陕西省科技计划项目(2011JM8031)

摘　　要：下模函数的最值问题在组合优化问题中有着广泛的应用,给出了具有剥分拟阵约束下非负非减下模函数最大值问题的近似算法,并讨论了所给算法的性能保证.Maximizing or minimizing submodular function has widely used in combinatorial optimization problem,in this paper,we present an approximation algorithm for the greedy algorithm of maximizing non-negative and non-decreasing submodular function subject to a partition matroid constraint,and discuss its performance guarantee.

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

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