摘要
为有效解决组合拍卖问题,从下模集函数最大值问题的基本结论出发,将部分穷举法与贪婪算法相结合,给出了一种求解组合拍卖问题的新算法——改进的贪婪算法,并从理论上证明了所给算法具有更好的性能保证.
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.
出处
《温州大学学报（自然科学版）》
2009年第3期32-36,共5页
Journal of Wenzhou University(Natural Science Edition)
基金
甘肃省自然科学基金(3ZS-042-B25-049)
关键词
组合拍卖
下模集函数
贪婪算法
Combinatorial Auction
Sub-modular Set Function
Greedy Algorithm
