【摘要】 提出了多维约束下下模函数最大值问题,分析其在组合优化中的重要应用.此问题是NP-难的,故给出了求解该问题的改进贪婪算法.最后,从理论上证明了这一算法的时间复杂性和性能保证.说明该算法是多项式时间近似算法,同时也具有较好的性能保证.更多还原

【Abstract】 The problem of maximizing a submodular set function with multiple constraints is considered,which has important application in combinatorial optimization theory. The problem is NP-hard and then an improved greedy algorithm is given.The time complexity and performance analysis of the algorithm are proved,then it is shown that the algorithm is polynomial time approximate and has a relatively good performance.更多还原