机构地区: 空军工程大学理学院应用数学物理系
出 处: 《德州学院学报》 2012年第4期9-10,共2页
摘 要: 下模函数的最值问题在组合优化问题中有着广泛的应用,给出了具有剥分拟阵约束下非负非减下模函数最大值问题的近似算法,并讨论了所给算法的性能保证. 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.