Abstract
In this paper we discuss the parallel implementation of the auction algorithm for the classical assignment problem. We show that the algorithm admits a totally asynchronous implementation and we consider several implementations on a shared memory machine, with varying degrees of synchronization. We also discuss and explore computationally the tradeoffs involved in using asynchronism to reduce the synchronization penalty.
Original language | English (US) |
---|---|
Pages (from-to) | 707-732 |
Number of pages | 26 |
Journal | Parallel Computing |
Volume | 17 |
Issue number | 6-7 |
DOIs | |
State | Published - Sep 1991 |
Externally published | Yes |
Keywords
- Assignment problem, auction algorithm
- computational results
- shared memory machines
- synchronous and asynchronous implementation
ASJC Scopus subject areas
- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computer Networks and Communications
- Computer Graphics and Computer-Aided Design
- Artificial Intelligence