The auction algorithm: A distributed relaxation method for the assignment problem
Annals of Operations ResearchPublished 1 December 1988Open access
Dimitri P. Bertsekas
Citations615
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
We propose a massively parallelizable algorithm for the classical assignment problem. The algorithm operates like an auction whereby unassigned persons bid simultaneously for objects thereby raising their prices. Once all bids are in, objects are awarded to the highest bidder. The algorithm can also be interpreted as a Jacobi — like relaxation method for solving a dual problem. Its (sequential) worst — case complexity, for a particular implementation that uses scaling, is O(NAlog(NC)), where N is the number of persons, A is the number of pairs of persons and objects that can be assigned to each other, and C is the maximum absolute object value. Computational results show that, for large problems, the algorithm is competitive with existing methods even without the benefit of parallelism. When executed on a parallel machine, the algorithm exhibits substantial speedup.
Keywords
Computer ScienceDecision SciencesEconomics, Econometrics and Finance
Naval Research Logistics QuarterlyThe Hungarian method for the assignment problem
12,574 Citations1955Harold W. Kuhn
American Mathematical MonthlyCombinatorial Optimization: Algorithms and Complexity.
6,028 Citations1984David Johnson, Christos H. Papadimitriou +1 more
Journal of the ACMTheoretical Improvements in Algorithmic Efficiency for Network Flow Problems
2,522 Citations1972Jack Edmonds, Richard M. Karp
Upper bounds on the number of steps in these algorithms are derived, and are shown to improve on the upper bounds of earlier algorithms.
International Journal of Game TheoryThe assignment game I: The core
1,716 Citations1971Lloyd S. Shapley, Martín Shubik
Mathematics of Operations ResearchThe Economics of Matching: Stability and Incentives
925 Citations1982Alvin E. Roth
The main focus of this paper is on determining the extent to which matching procedures can be designed which give agents the incentive to honestly reveal their preferences, and which produce stable matches.
Journal of the ACMAsynchronous Iterative Methods for Multiprocessors
521 Citations1978Gérard M. Baudet
A class of asynchronous iterative methods is presented for solving a system of equations corresponding to a parallel implementation on a multiprocessor system with no synchronization between cooperating processes to show clearly the advantage of purely asynchronous Iterative methods.
Management ScienceNETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems
418 Citations1974Darwin Klingman, A. Napier +1 more
The development, implementation, and availability of a computer program for generating a variety of feasible network problems together with a set of benchmarked problems derived from it, called NETGEN, are described.
COMBINATORICAA strongly polynomial minimum cost circulation algorithm
375 Citations1985Éva Tardos
A new algorithm is presented for the minimum cost circulation problem that is strongly polynomial, that is, the number of arithmetic operations isPolynomial in thenumber of nodes, and is independent of both costs and capacities.
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.
Mathematical ProgrammingDistributed asynchronous computation of fixed points
228 Citations1983Dimitri P. Bertsekas
A general convergence theorem is provided for algorithms of this type including the calculation of fixed points of contraction and monotone mappings arising in linear and nonlinear systems of equations, optimization problems, shortest path problems, and dynamic programming.
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.
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.
SIAM Journal on Control and OptimizationRelaxation Methods for Network Flow Problems with Convex Arc Costs
106 Citations1987Dimitri P. Bertsekas, Patrick Hosein +1 more
This work studies the convergence of a dual Gauss-Seide! type relaxation method that is well suited for parallel computation for the standard single commodity network flow problem with both linear and strictly convex possibly nondifferentiable arc costs.
Operations ResearchSolving the Assignment Problem by Relaxation
103 Citations1980Ming S. Hung, Walter O. Rom
This paper presents a new algorithm for solving the assignment problem based on a scheme of relaxing the given problem into a series of simple network flow transportation problems for each of which an optimal solution can be easily obtained.
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 ProgrammingOn the computational behavior of a polynomial-time network flow algorithm
66 Citations1992Robert G. Bland, David L. Jensen
A variation on the Edmonds-Karp scaling approach to the minimum cost network flow problem is examined, and median and mean execution times are predictable with surprising accuracy for all of the three codes and all three distributions from which test problems were generated.
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.
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.
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.
Annals of Operations ResearchNonlinear network optimization on a massively parallel connection machine
46 Citations1988Stavros A. Zenios, R. A. Lasken
This paper describes the implementation of a distributed relaxation algorithm for strictly convex network problems on a massively parallel computer and reports computational results with a series of stick percolation and quadratic transportation problems.
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
Mathematical ProgrammingEfficient dual simplex algorithms for the assignment problem
41 Citations1986Donald 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.
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.
Annals of Operations ResearchRelaxation techniques for strictly convex network problems
27 Citations1986Stavros A. Zenios, John M. Mulvey
Gauss—Seidel type relaxation techniques are applied in the context of strictly convex pure networks with separable cost functions for solving the linear network problem and its dual as a pair of monotropic programming problems.
Annals of Operations ResearchRelaxation techniques for strictly convex network problems
6 Citations1986Stavros A. Zenios, John M. Mulvey
The algorithm is an extension of the Bertsekas—Tseng approach for solving the linear network problem and its dual as a pair of monotropic programming problems and is extended to cover the class of generalized network problems.