The Auction Algorithm for Assignment and Other Network Flow Problems: A Tutorial
INFORMS Journal on Applied AnalyticsPublished 1 August 1990
Dimitri P. Bertsekas
Citations225
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.
Abstract
The auction algorithm is an intuitive method for solving the classical assignment problem. It outperforms substantially its main competitors for important types of problems, both in theory and in practice and is also naturally well suited for parallel computation. I derive the algorithm from first principles, explain its computational properties, and discuss its extensions to transportation and transshipment problems.
Keywords
Social SciencesDecision SciencesEngineering
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
Operations ResearchThe Traveling-Salesman Problem and Minimum Spanning Trees
1,443 Citations1970Michael Held, Richard M. Karp
It is shown that maxπwπ = C* precisely when a certain well-known linear program has an optimal solution in integers.
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.
Mathematical ProgrammingThe traveling-salesman problem and minimum spanning trees: Part II
1,017 Citations1971Michael Held, Richard M. Karp
An efficient iterative method for approximating this bound closely from below is presented, and a branch-and-bound procedure based upon these considerations has easily produced proven optimum solutions to all traveling-salesman problems presented to it.
Annals of Operations ResearchThe auction algorithm: A distributed relaxation method for the assignment problem
615 Citations1988Dimitri 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.
Operations ResearchRelaxation Methods for Minimum Cost Ordinary and Generalized Network Flow Problems
194 Citations1988Dimitri P. Bertsekas, Paul Tseng
These algorithms are based on iterative improvement of a dual cost and operate in a manner that is reminiscent of coordinate ascent and Gauss-Seidel relaxation methods, and are found to be several times faster on standard benchmark problems, and faster by an order of magnitude on large, randomly generated problems.
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.
Parallel ComputingParallel synchronous and asynchronous implementations of the auction algorithm
175 Citations1991Dimitri P. Bertsekas, David A. Castañón
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.
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.
Mathematical ProgrammingFinding minimum-cost flows by double scaling
126 Citations1992Ravindra K. Ahuja, Andrew V. Goldberg +2 more
This paper combines several techniques to yield an algorithm running in O(nm(log logU) log(nC) time on networks withn vertices, m edges, maximum arc capacityU, and maximum arc cost magnitudeC, and discusses a capacity-bounding approach 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.
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.
Distributed relaxation methods for linear network flow problems
49 Citations1986Dimitri P. Bertsekas
A dual problem which is unconstrained, piecewise linear, and involves a dual variable for each node is formulated, and a dual algorithm that resembles a Gauss-Seidel relaxation method is proposed.
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.
INFORMS Journal on ComputingParallel Asynchronous Hungarian Methods for the Assignment Problem
37 Citations1993Dimitri P. Bertsekas, David A. Castañón
The validity of the Hungarian method for solving the classical assignment problem is shown, and it is demonstrated computationally that an asynchronous implementation is often faster than its synchronous counterpart.
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.
RePEc: Research Papers in EconomicsA PARALLEL SHORTEST PATH ALGORITHM FOR THE ASSIGNMENT PROBLEM
27 Citations1989Egon Balas, D. Miller +2 more
ComputingA parallel shortest path algorithm
20 Citations1988Th. Mohr, C. Pasche
A new algorithm to find the shortest path between a pair of nodes is presented that expands the search from origin and destination simultaneously, on the other hand it uses a lower bound for the shortest route to guide this search.
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?
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.