剖分拟阵约束下求解下模函数最大值问题的一种贪婪算法  

A Greedy Algorithm for Maximizing Submodular Set Function under Partition Matroid Constraint

作　　者：罗亮[1] 崔俊峰[2] 樊亮[1] 贾欣鑫[1] 何尚录[1] 

机构地区：[1]兰州交通大学数理与软件工程学院,兰州730070 [2]甘肃陇南师范高等专科学校,甘肃成县742500

出　　处：《淮阴工学院学报》2009年第3期6-10,共5页Journal of Huaiyin Institute of Technology

摘　　要：给出了求解剖分拟阵约束下,下模函数最大值问题的一种新的近似算法,这一算法是改进的贪婪算法,即将局部搜索法与贪婪算法相结合,使其整体具有更好的性能保证。同时从理论上证明了这一算法的可靠性。最后通过具体算例验证了算法的有效性。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.

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

分 类 号：O224[理学—运筹学与控制论]