An efficient local search algorithm for the winner determination problem

doi:10.1007/s10732-017-9344-y

CORC > 计算技术研究所 > 中国科学院计算技术研究所 > 中国科学院计算技术研究所期刊论文 > 英文

	An efficient local search algorithm for the winner determination problem
	Zhang, Haochen 4; Cai, Shaowei 1; Luo, Chuan 2,3; Yin, Minghao 4
刊名	JOURNAL OF HEURISTICS
	2017-10-01
卷号	23 期号:5 页码:367-396
关键词	Winner determination problem Local search Configuration checking Pseudo-tie mechanism
ISSN号	1381-1231
DOI	10.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
语种	英语
出版者	SPRINGER
WOS记录号	WOS:000409967800004
内容类型	期刊论文
源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.