An efficient local search algorithm for the winner determination problem

doi:10.1007/s10732-017-9344-y

	An efficient local search algorithm for the winner determination problem
	Zhang, Haochen 1; Cai, Shaowei 2; Luo, Chuan 3,4; Yin, Minghao 1
	2017-10-01
发表期刊	JOURNAL OF HEURISTICS
ISSN	1381-1231
卷号	23 期号:5 页码:367-396
摘要	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.
关键词	Winner determination problem Local search Configuration checking Pseudo-tie mechanism
DOI	10.1007/s10732-017-9344-y
收录类别	SCI
语种	英语
资助项目	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类目	Computer Science, Artificial Intelligence ; Computer Science, Theory & Methods
WOS记录号	WOS:000409967800004
出版者	SPRINGER
引用统计	被引频次：5[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/6734
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Yin, Minghao
作者单位	1.Northeast Normal Univ, Sch Comp Sci & Informat Technol, Changchun 130024, Jilin, Peoples R China 2.Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing 100190, Peoples R China 3.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China 4.State Key Lab Math Engn & Adv Comp, Wuxi 214125, 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.