Warning: pg_query(): Query failed: ERROR: missing chunk number 0 for toast value 29512337 in pg_toast_2619 in /dati/webiit-old/includes/database.pgsql.inc on line 138 Warning: ERROR: missing chunk number 0 for toast value 29512337 in pg_toast_2619 query: SELECT data, created, headers, expire, serialized FROM cache_page WHERE cid = 'https://www-old.iit.cnr.it/node/614' in /dati/webiit-old/includes/database.pgsql.inc on line 159 Warning: pg_query(): Query failed: ERROR: missing chunk number 0 for toast value 29512337 in pg_toast_2619 in /dati/webiit-old/includes/database.pgsql.inc on line 138 Warning: ERROR: missing chunk number 0 for toast value 29512337 in pg_toast_2619 query: SELECT data, created, headers, expire, serialized FROM cache_page WHERE cid = 'https://www-old.iit.cnr.it/node/614' in /dati/webiit-old/includes/database.pgsql.inc on line 159 An Optimal Multiprocessor Combinatorial Auction Solver | IIT - CNR - Istituto di Informatica e Telematica
IIT Home Page CNR Home Page

An Optimal Multiprocessor Combinatorial Auction Solver

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


COMPUTERS & OPERATIONS RESEARCH (30235J0), 2009

Autori esterni: Shouxi Yang (Department of Computer Science, The University of Iowa, Iowa City, USA), Alberto Maria Segre (Department of Computer Science, The University of Iowa, Iowa City, USA)
Autori IIT:

Tipo: Articoli su riviste ISI
Area di disciplina: Information Technology and Communication Systems
Accettato per la pubblicazione Available online 27 August 2007 Da pagina 149 a pagina 166

Attività: Economia computazionale