摘要
为有效解决组合拍卖问题,从基约束条件下,下模函数最大值问题的基本结论出发,逐步过渡到求解组合拍卖问题的贪婪算法,给出一种新的近似算法,分析了该算法的性能保证。该算法是一种改进的贪婪算法,即将部分穷举法与贪婪算法结合,从而使其具有更好的性能保证,并从理论上证明了该算法的可靠性和有效性。
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.
出处
《黑龙江科技学院学报》
CAS
2008年第5期382-384,共3页
Journal of Heilongjiang Institute of Science and Technology
关键词
贪婪算法
组合拍卖
下模函数
性能保证
greedy algorithm
combination of auction
submodular set function
performance guarantee
