Parallel synchronous and asynchronous implementations of the auction algorithm

Dimitri P. Bertsekas, David A. Castañon

Research output: Contribution to journalArticlepeer-review

111 Scopus citations


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 languageEnglish (US)
Pages (from-to)707-732
Number of pages26
JournalParallel Computing
Issue number6-7
StatePublished - Sep 1991
Externally publishedYes


  • 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


Dive into the research topics of 'Parallel synchronous and asynchronous implementations of the auction algorithm'. Together they form a unique fingerprint.

Cite this