کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
474841 | 699151 | 2009 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An optimal multiprocessor combinatorial auction solver
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A combinatorial auction (CA) is an auction that permits bidders to bid on bundles of goods rather than just a single item. Unfortunately, winner determination for CAs is known to be NP-hard. In this paper, we propose a distributed algorithm to compute optimal solutions to this problem. The algorithm uses nagging, a technique for parallelizing search in heterogeneous distributed computing environments. Here, we show how nagging can be used to parallelize a branch-and-bound algorithm for this problem, and provide empirical results supporting both the performance advantage of nagging over more traditional partitioning methods as well as the superior scalability of nagging to larger numbers of processors.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 36, Issue 1, January 2009, Pages 149–166
Journal: Computers & Operations Research - Volume 36, Issue 1, January 2009, Pages 149–166
نویسندگان
Shouxi Yang, Alberto Maria Segre, Bruno Codenotti,