求解下模函数最大值问题的近似算法及其性能保证  

The Greedy Algorithm and Its Performance Guarantees for Solving Maximization of Submodular Function

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

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

出　　处：《上海第二工业大学学报》2011年第1期26-28,共3页Journal of Shanghai Polytechnic University

摘　　要：下模函数的最值问题在组合优化问题中有着广泛的应用,给出了具有拟阵交构成的独立系统约束下模函数的最大值问题的近似算法,并讨论了所给算法的性能保证。Maximizing or minimizing submodular function is widely used in combinatorial optimi-zation problem,in this paper,we present an approximation algorithm for the greedy algorithm of maximizing submodular function subject to an independence system that can be expressed as the intersection of a finite number of matroids,and discuss its performance guarantee.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]