کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
382942 660798 2015 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Solving the winner determination problem via a weighted maximum clique heuristic
ترجمه فارسی عنوان
حل مسئله تعیین برنده را از طریق یک حداکثر ارزیابی بالایی از وزن
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
چکیده انگلیسی


• The winner determination problem (WDP) is a key issue in combinatorial auctions with many applications.
• We recast the WDP to a clique problem (MWCP) and solve it with a recent clique heuristic.
• The approach is assessed on three test suites of 530 benchmark instances.
• The approach outperforms the current best specific WDP heuristics in quality and efficiency.
• The approach is an useful alternative to solve the WDP in respect to the CPLEX solver.

Combinatorial auctions (CAs) where bidders can bid on combinations of items is an important model in many application areas. CAs attract more and more attention in recent years due to its relevance to fast growing electronic business applications. In this paper, we study the winner determination problem (WDP) in CAs which is known to be NP-hard and thus computationally difficult in the general case. We develop a solution approach for the WDP by recasting the WDP into the maximum weight clique problem (MWCP) and solving the transformed problem with a recent heuristic dedicated to the MWCP. The computational experiments on a large range of 530 benchmark instances show that the clique-based approach for the WDP not only outperforms the current best performing WDP heuristics in the literature both in terms of solution quality and computation efficiency, but also competes very favorably with the powerful CPLEX solver.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Expert Systems with Applications - Volume 42, Issue 1, January 2015, Pages 355–365
نویسندگان
, ,