| 基于有穷损害优先法求解组合拍卖竞胜标问题研究 |
| |
| 引用本文： | 钱巍,冯玉强,唐振宇.基于有穷损害优先法求解组合拍卖竞胜标问题研究[J].运筹与管理,2012,21(3):144-147. |
| |
| 作者姓名： | 钱巍 冯玉强 唐振宇 |
| |
| 作者单位： | 1. 哈尔滨工业大学经济管理学院,黑龙江哈尔滨150001;东北农业大学经济管理学院,黑龙江哈尔滨150030
2. 哈尔滨工业大学经济管理学院,黑龙江哈尔滨,150001 |
| |
| 基金项目： | 国家自然科学基金资助项目，黑龙江省自然科学基金资助项目 |
| |
| 摘 要： | 迄今为止,组合拍卖竞胜标问题并不存在一个多项式时间复杂度的算法,其计算复杂性与拍卖效率之间的矛盾一直是影响组合拍卖广泛应用的主要障碍。它是一个NP难问题,也是组合拍卖机制设计中的难题之一。而有穷损害优先方法是纯粹递归论中的一个十分重要的现代方法,特别对NP难问题求解算法的设计,对研究依复杂度决定的偏序结构的构造是一个很基本的有用工具。因此,本文提出根据组合拍卖的内在特性,将各不同的拍卖商品按照拍卖机制的要求,并结合其自身的协同价值等因素,设定一个优先序,然后采用有穷损害优先法有效有序地解决。
|
| 关 键 词： | 组合拍卖 竞胜标确定 NP难问题 有穷损害优先法 |
Solution to the Winner Determination Problem in Combinatorial Auctions By Finite Injury Priority Method |
| |
| QIAN Wei
,
FENG YU-Qiang
,
TANG Zhen-Yu.Solution to the Winner Determination Problem in Combinatorial Auctions By Finite Injury Priority Method[J].Operations Research and Management Science,2012,21(3):144-147. |
| |
| Authors: | QIAN Wei FENG YU-Qiang TANG Zhen-Yu |
| |
| Institution: | 1(1.School of Management,Harbin Institute of Technology,Harbin 150001,China;2.Department of Economics management,Northeast Agricultural University,Harbin 150030,China) |
| |
| Abstract: | So far,the winner determination problem in combinatorial auctions has not had a polynomial time complexity algorithm.It is an NP-hard problem.The finite injury priority method is one of the very important modern methods in recursion theory.In particular,it is a very useful tool or designing the NP-hard problem solving algorithm according to the complexity of the of the partial order structure.So,an approximate algorithm is proposed for solving the well-known NP hard problem-the winner determination problem in combinatorial auctions. |
| |
| Keywords: | combinatorial auctions the winner determination problem NP-hard problem finite injury priority method |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
