摘要
给出了求解剖分拟阵约束下,下模函数最大值问题的一种新的近似算法,这一算法是改进的贪婪算法,即将局部搜索法与贪婪算法相结合,使其整体具有更好的性能保证。同时从理论上证明了这一算法的可靠性。最后通过具体算例验证了算法的有效性。
This paper presents a new approximation algorithm for maximizing submodular set function under partition matroid constraint. The algorithm is an improved greedy algorithm which combines the part of searching method with the greedy algorithm, thus making it a better performance guarantee. At the same time, the reliability of this algorithm is theoretically proved. Finally, the effectiveness of the algorithm is verified with the specific example.
出处
《淮阴工学院学报》
CAS
2009年第3期6-10,共5页
Journal of Huaiyin Institute of Technology
关键词
组合最优化问题
剖分拟阵
下模函数
近似算法
性能保证
combinatorial optimization problem
partition matroid
submodular set function
greedy algorithm
performance guarantee
