求解组合拍卖问题最大值的贪婪算法  

Greedy algorithm for maximizing combinatorial auction problem

作　　者：罗亮[1] 贾欣鑫[1] 何尚录[1] 

机构地区：[1]兰州交通大学数理与软件工程学院,兰州730070

出　　处：《黑龙江科技学院学报》2008年第5期382-384,共3页Journal of Heilongjiang Institute of Science and Technology

摘　　要：为有效解决组合拍卖问题,从基约束条件下,下模函数最大值问题的基本结论出发,逐步过渡到求解组合拍卖问题的贪婪算法,给出一种新的近似算法,分析了该算法的性能保证。该算法是一种改进的贪婪算法,即将部分穷举法与贪婪算法结合,从而使其具有更好的性能保证,并从理论上证明了该算法的可靠性和有效性。This paper presents a new approximation algorithm for solving combinatorial auction problem effectively by applying the result of maximizing submodular problem under cardinality constraint. The algorithm is an improved greedy algorithm which combines the part of enumeration method with the greedy algorithm, thus making it a better performance guarantee. At the same time, the reliability and effect of this algorithm are theoretically proved.

关 键 词：贪婪算法 组合拍卖 下模函数 性能保证 

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