| 求解组合拍卖问题最大值的贪婪算法 |
| |
| 引用本文： | 罗亮,贾欣鑫,何尚录.求解组合拍卖问题最大值的贪婪算法[J].黑龙江科技学院学报,2008,18(5). |
| |
| 作者姓名： | 罗亮 贾欣鑫 何尚录 |
| |
| 作者单位： | 兰州交通大学,数理与软件工程学院,兰州,730070 |
| |
| 摘 要： | 为有效解决组合拍卖问题,从基约束条件下,下模函数最大值问题的基本结论出发,逐步过渡到求解组合拍卖问题的贪婪算法,给出一种新的近似算法,分析了该算法的性能保证.该算法是一种改进的贪婪算法,即将部分穷举法与贪婪算法结合,从而使其具有更好的性能保证,并从理论上证明了该算法的可靠性和有效性.
|
| 关 键 词： | 贪婪算法 组合拍卖 下模函数 性能保证 |
Greedy algorithm for maximizing combinatorial auction problem |
| |
| LUO Liang,JIA Xinxin,HE Shanglu.Greedy algorithm for maximizing combinatorial auction problem[J].Journal of Heilongjiang Institute of Science and Technology,2008,18(5). |
| |
| Authors: | LUO Liang JIA Xinxin HE Shanglu |
| |
| Institution: | LUO Liang,JIA Xinxin,HE Shanglu(School of Mathematics,Physics , Software Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China) |
| |
| Abstract: | 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. |
| |
| Keywords: | greedy algorithm combination of auction submodular set function performance guarantee |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
