求解组合拍卖问题的一种贪婪算法  

Greedy Algorithm for Solving Combinatorial Auction Issue

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

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

出　　处：《温州大学学报（自然科学版）》2009年第3期32-36,共5页Journal of Wenzhou University(Natural Science Edition)

基　　金：甘肃省自然科学基金(3ZS-042-B25-049)

摘　　要：为有效解决组合拍卖问题,从下模集函数最大值问题的基本结论出发,将部分穷举法与贪婪算法相结合,给出了一种求解组合拍卖问题的新算法——改进的贪婪算法,并从理论上证明了所给算法具有更好的性能保证.By applying the conclusions for sub-modular set function＇s maximum value, a new approximation algorithm for combinatorial auction issue was presented. The algorithm is an improved greedy one which has achieved a better performance guarantee by combining the part of enumeration method with the greedy algorithm. At the same time, the reliability and effect of this algorithm were theoretically proved.

关 键 词：组合拍卖 下模集函数 贪婪算法 

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