中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
An efficient local search algorithm for the winner determination problem

文献类型：期刊论文

作者Zhang, Haochen4; Cai, Shaowei1; Luo, Chuan2,3; Yin, Minghao4
刊名JOURNAL OF HEURISTICS
出版日期2017-10-01
卷号23期号:5页码:367-396
关键词Winner determination problem Local search Configuration checking Pseudo-tie mechanism
ISSN号1381-1231
DOI10.1007/s10732-017-9344-y
英文摘要Combinatorial auction, which allows bidders to bid on combinations of items, is an important type of market mechanism. The winner determination problem (WDP) has extensive applications in combinatorial auctions, and attracts more and more attention due to its strong relevance to business. However, this problem is intractable in theory as it has been proven to be NP-hard, and is also a challenging combinatorial optimization problem in practice. This paper is devoted to designing an efficient heuristic algorithm for solving the WDP. This proposed heuristic algorithm dubbed abcWDP is based on an effective yet simple local search framework, and equipped with three novel strategies, i.e., configuration checking, free-bid exploiting, and pseudo-tie mechanism. Extensive computational experiments on a broad range of benchmarks demonstrate that abcWDP performs much better than state-of-the-art algorithms and CPLEX in terms of both revenue and running time. More encouragingly, our abcWDP algorithm as a sequential algorithm even achieves better computational results than the multi-thread implemented algorithm , which confirms its efficiency.
资助项目National Natural Science Foundation of China[61370156] ; National Natural Science Foundation of China[61503074] ; National Natural Science Foundation of China[61502464] ; Program for New Century Excellent Talents in University[NCET-13-0724] ; Open Project Program of the State Key Laboratory of Mathematical Engineering and Advanced Computing[2016A06]
WOS研究方向Computer Science
语种英语
WOS记录号WOS:000409967800004
出版者SPRINGER
源URL[http://119.78.100.204/handle/2XEOYT63/6733]  
专题中国科学院计算技术研究所期刊论文_英文
通讯作者Yin, Minghao
作者单位1.Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing 100190, Peoples R China
2.State Key Lab Math Engn & Adv Comp, Wuxi 214125, Peoples R China
3.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China
4.Northeast Normal Univ, Sch Comp Sci & Informat Technol, Changchun 130024, Jilin, Peoples R China
推荐引用方式
GB/T 7714		 Zhang, Haochen,Cai, Shaowei,Luo, Chuan,et al. An efficient local search algorithm for the winner determination problem[J]. JOURNAL OF HEURISTICS,2017,23(5):367-396.
APA Zhang, Haochen,Cai, Shaowei,Luo, Chuan,&Yin, Minghao.(2017).An efficient local search algorithm for the winner determination problem.JOURNAL OF HEURISTICS,23(5),367-396.
MLA Zhang, Haochen,et al."An efficient local search algorithm for the winner determination problem".JOURNAL OF HEURISTICS 23.5(2017):367-396.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。