Journal article
An optimal multiprocessor combinatorial auction solver
Computers & operations research, Vol.36(1), pp.149-166
2009
DOI: 10.1016/j.cor.2007.08.001
Abstract
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.
Details
- Title: Subtitle
- An optimal multiprocessor combinatorial auction solver
- Creators
- Shouxi Yang - University of IowaAlberto Maria Segre - University of IowaBruno Codenotti - Informatica
- Resource Type
- Journal article
- Publication Details
- Computers & operations research, Vol.36(1), pp.149-166
- Publisher
- Elsevier Ltd
- DOI
- 10.1016/j.cor.2007.08.001
- ISSN
- 0305-0548
- eISSN
- 1873-765X
- Language
- English
- Date published
- 2009
- Academic Unit
- Nursing; Fraternal Order of Eagles Diabetes Research Center; Computer Science
- Record Identifier
- 9984259464102771
Metrics
2 Record Views