Parallel synchronous and asynchronous implementations of the auction algorithm
Parallel ComputingPublished 1 September 1991
Dimitri P. Bertsekas, David A. Castañón
Citations175
SJR quartileQ2
SJR score0.54
SNIP1.30
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The parallel implementation of the auction algorithm for the classical assignment problem is discussed and the tradeoffs involved in using asynchronism to reduce the synchronization penalty are explored.
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.
Keywords
Computer ScienceDecision SciencesEconomics, Econometrics and Finance
Naval Research Logistics QuarterlyThe Hungarian method for the assignment problem
12,574 Citations1955Harold W. Kuhn
Society for Industrial and Applied Mathematics eBooksIterative Solution of Nonlinear Equations in Several Variables
6,875 Citations2000J. M. Ortega, Werner C. Rheinboldt
Convergence of Minimization Methods An Annotated List of Basic Reference Books Bibliography Author Index Subject Index.
American Mathematical MonthlyCombinatorial Optimization: Algorithms and Complexity.
6,028 Citations1984David Johnson, Christos H. Papadimitriou +1 more
Journal of the Society for Industrial and Applied MathematicsAlgorithms for the Assignment and Transportation Problems
3,984 Citations1957James Munkres
ComputingA shortest augmenting path algorithm for dense and sparse linear assignment problems
1,231 Citations1987R. Jonker, A. Volgenant
A shortest augmenting path algorithm for the linear assignment problem that contains new initialization routines and a special implementation of Dijkstra's shortest path method is developed.
Annals of Operations ResearchThe auction algorithm: A distributed relaxation method for the assignment problem
615 Citations1988Dimitri P. Bertsekas
Mathematics of ComputationLinear Network Optimization: Algorithms and Codes.
323 Citations1993Donald K. Wagner, Dimitri P. Bertsekas
Mathematical ProgrammingA new algorithm for the assignment problem
285 Citations1981Dimitri P. Bertsekas
In a large number of randomly generated problems the algorithm has consistently outperformed an efficiently coded version of the Hungarian method by a broad margin.
Solving minimum-cost flow problems by successive approximation
213 Citations1987Andrew Goldberg, Robert E. Tarjan
This work introduces a framework for solving minimum-cost flow problems and shows how to extend techniques developed for the maximum flow problem to improve the quality of a solution.
Annals of Operations ResearchThe auction algorithm for the transportation problem
182 Citations1989Dimitri P. Bertsekas, David A. Castañón
The idea is to convert the transportation problem into an assignment problem, and then to modify the auction algorithm to exploit the special structure of this problem.
Annals of Operations ResearchAlgorithms and codes for the assignment problem
161 Citations1988G. Carpaneto, Silvano Martello +1 more
This paper analyzes the most efficient algorithms for the Linear Min-Sum Assignment Problem and shows that they derive from a common basic procedure, and evaluates the computational complexity and the average performance on randomly-generated test problems.
Mathematical ProgrammingThe alternating basis algorithm for assignment problems
154 Citations1977R. S. Barr, Fred Glover +1 more
A new primal extreme point algorithm for solving assignment problems which both circumvents and exploits degeneracy is presented, and is substantially more efficient than previously developed primal and primal-dual extreme point methods for assignment problems.
Operations ResearchSignature Methods for the Assignment Problem
128 Citations1985Michel Balinski
This paper uses signatures to describe a method for finding optimal assignments that terminates in at most n-1n-2/2 pivot steps and takes at most On3 work.
DSpace@MIT (Massachusetts Institute of Technology)EFFICIENT GRAPH ALGORITHMS FOR SEQUENTIAL AND PARALLEL COMPUTERS
121 Citations1987Andrew V. Goldberg
This thesis proves lower bounds on the parallel complexity of the maximal independent set problem and the problem of 2-coloring a rooted tree, and introduces a frame work that allows the generalization of the maximum flow techniques to the minimum-cost flow problem.
SIAM Journal on Control and OptimizationDistributed Asynchronous Relaxation Methods for Convex Network Flow Problems
111 Citations1987Dimitri P. Bertsekas, Didier El Baz
The structure of the dual allows the successful application of a distributed asynchronous method whereby relaxation iterations are carried out in parallel by several processors in arbitrary order and with arbitrarily large interprocessor communication delays.
Mathematical ProgrammingDual coordinate step methods for linear network flow problems
96 Citations1988Dimitri P. Bertsekas, Jonathan Eckstein
A class of recently-proposed linear-cost network flow methods which are amenable to distributed implementation using the notion ofε-complementary slackness is reviewed, and two specific methods, theε-relaxation algorithm for the minimum-cost flow problem, and the auction algorithms for the assignment problem are presented.
Mathematical ProgrammingA competitive (dual) simplex method for the assignment problem
87 Citations1986Michel Balinski
A dual simplex method for the assignment problem leaves open to choice the activity (i,j) of rowi and columnj that is to be dropped in pivoting so long asxij < 0.1, and it is argued that on average the number of pivots is at mostn logn.
A distributed asynchronous relaxation algorithm for the assignment problem
67 Citations1985Dimitri P. Bertsekas
A distributed algorithm for solving the classical linear cost assignment problem that employs exclusively pure relaxation steps whereby the prices of sources and sinks are changed individually on the basis of only local node price information.
IFAC Proceedings VolumesDistributed Asynchronous Relaxation Methods for Linear Network Flow Problems
66 Citations1987Dimitri P. Bertsekas, Jonathan Eckstein
Finite convergence of a totally asynchronous (chaotic), distributed version of the massively parallelizable algorithm in which some processors compute faster than others, some processors communicate faster thanOthers, and there can be arbitrarily large communication delays is shown.
Mathematical ProgrammingEfficient dual simplex algorithms for the assignment problem
56 Citations1985Donald Goldfarb
Efficient algorithms based upon Balinski's signature method are described for solving then × n assignment problem and are shown to have computational bounds of O(n3) space and O(mn + n2 logn) time in the worst case.
Annals of Operations ResearchThe shortest augmenting path method for solving assignment problems — Motivation and computational experience
56 Citations1985Ulrich Derigs
This paper discusses the shortest augmenting path method for solving assignment problems and introduces this basic concept using matching theory, which naturally leads to a new, highly efficient hybrid approach for solving large-scale dense assignment problems.
Operations ResearchImplementation and Testing of a Primal-Dual Algorithm for the Assignment Problem
52 Citations1983Leon F. McGinnis
A detailed development for a computationally efficient primal-dual algorithm and extensive computational comparisons to primal simplex algorithms are presented.
Mathematical ProgrammingA unified framework for primal-dual methods in minimum cost network flow problems
48 Citations1985Dimitri P. Bertsekas
A broad class of algorithms for finding a minimum cost flow in a capacitated network that maintains primal feasibility with respect to capacity constraints, while trying to satisfy the conservation of flow equation at each node by means of a wide variety of procedures based on flow augmentation, price adjustment, and ascent of a dual functional.
INFOR Information Systems and Operational ResearchA Successive Shortest Path Algorithm for The Assignment Problem
46 Citations1982Michael Engquist
Computational results are presented which show this implementation of SSP to be substantially more efficient than several recently developed codes including the best primal simplex code.
Operations ResearchTechnical Note—A Polynomial Simplex Method for the Assignment Problem
44 Citations1983Ming S. Hung
Journal of the Operational Research SocietyStudies on Graphs and Discrete Programming
44 Citations1982John R. Beaumont
Mathematical programming studiesThreshold assignment algorithm
32 Citations1986Fred Glover, Randy Glover +1 more
Preliminary computational findings indicate that the threshold assignment algorithm is much faster than the primal simplex algorithm for solving assignment problems.
Massively parallel auction algorithms for the assignment problem
29 Citations2002Joel Wein, Stavros A. Zenios
Alternative approaches to the massively parallel implementation of D.P. Bertsekas' auction algorithm on the Connection Machine CM2 are discussed, with the most efficient implementation a hybrid Jacobi/Gauss-Seidel implementation.
Parallel ComputingSynchronous and asynchronous implementations of relaxation algorithms for nonlinear network optimization
28 Citations1991Emmanuel D. Chajakis, Stavros A. Zenios
It is demonstrated that the most effective parallel implementation is an asynchronous one, for which speedup factors of up to 7.2 are achieved on an 8 processor system.
RePEc: Research Papers in EconomicsA PARALLEL SHORTEST PATH ALGORITHM FOR THE ASSIGNMENT PROBLEM
27 Citations1989Egon Balas, D. Miller +2 more
INFORMS Journal on ComputingPerformance Characteristics of the Jacobi and the Gauss-Seidel Versions of the Auction Algorithm on the Alliant FX/8
19 Citations1991David N. Kempka, Jeffery L. Kennington +1 more
Questions arise regarding the relative performance of these two versions of the auction algorithm: How will their performances be affected by changes in problem size, cost range, and problem data?
A computational experience with distributed asynchronous iterative methods for convex network flow problems
16 Citations2003Didier El Baz
The computation, which was carried out on a network of four transputers, shows that distributed asynchronous implementation of relaxation methods permits substantial speedup to be obtained and the results show that distributedynchronous relaxation methods are not really efficient compared with the steepest descent method and its distributed asynchronous version.
North-Holland mathematics studiesA Recursive Method for Solving Assignment Problems
15 Citations1981Gerald L. Thompson
Extensive computational experience on the DEC-20 computer shows the recursive algorithm to be competitive for at least some kinds of assignment problems, and a dimension expanding rather than an improvement method such as as the simplex.
University of North Texas Digital Library (University of North Texas)Beyond "'Speedup": Performance Analysis of Parallel Programs
9 Citations1987Kenneth W. Dritz, James M. Boyle
This paper addresses the problem of measuring and analyzing the performance of fine-grained parallel programs running on shared-memory multiprocessors by identifying the chief factor preventing linear speedup.