摘要
次模集函数的最值问题在组合优化问题中有广泛应用,次模集函数的增减性对该问题的分析具有一定的简化作用.给出了求解非减次模集函数最大值问题的一种近似算法,并讨论了所给算法的性能保证.
Maximizing or minimizing a submodular set function has a wide use in combinatorial optimization problem, and non-increasing or non-decreasing of these set function are very helpful in analyzing these problems. In this paper, we present an approximation algorithm for maximizing a non-increasing submodular set function, and discuss its performance guarantee.
出处
《西南民族大学学报（自然科学版）》
CAS
2009年第1期35-40,共6页
Journal of Southwest Minzu University(Natural Science Edition)
基金
北方民族大学科研资助项目(NO.2007Y044)
关键词
组合优化问题
次模集函数
近似算法
性能保证
combinatorial optimization problem
submodular set function
approximation algorithm
performance guarantee
