Efficient dual simplex algorithms for the assignment problem
- Published: November 1985
- Volume 33 , pages 187–203, ( 1985 )
Cite this article
- D. Goldfarb 1
260 Accesses
52 Citations
Explore all metrics
Efficient algorithms based upon Balinski's signature method are described for solving the n × n assignment problem. These algorithms are special variants of the dual simplex method and are shown to have computational bounds of O( n 3 ). Variants for solving sparse assignment problems with m arcs that require O( m ) space and O( mn + n 2 log n ) time in the worst case are also presented.
This is a preview of subscription content, log in via an institution to check access.
Access this article
Subscribe and save.
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Price includes VAT (Russian Federation)
Instant access to the full article PDF.
Rent this article via DeepDyve
Institutional subscriptions
Similar content being viewed by others
A Variant of the Dual Simplex Method for a Linear Semidefinite Programming Problem
Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem.
Techniques for Submodular Maximization
A.V. Aho, J.E. Hopcroft and J.D. Ullman, The design and analysis of computer algorithms (Addison-Wesley, Reading, MA, 1974).
Google Scholar
M.L. Balinski, “Signature methods for the assignment problem”, to appear in Operations Research.
M.L. Balinski and R.E. Gomory, “A primal method for the assignment and transportation problems”, Management Science 10 (1964) 578–593.
R. Barr, F. Glover and D. Klingman, “The alternating path basis algorithm for assignment problems”, Mathematical Programming 13 (1977) 1–13.
D. Bertsekas, “A new algorithm for the assignment problem”, Mathematical Programming 21 (1981) 152–171.
W.H. Cunningham, “A network simplex method”, Mathematical Programming 11 (1976) 105–116.
W.H. Cunningham and A.B. Marsh, III, “A primal algorithm for optimum matching”, Mathematical Programming Study 8 (1978) 50–72.
G.B. Dantzig, “Application of the Simplex Method to a Transportation Problem”, in: T.C. Koopmans, ed., Activity analysis of production and allocation (Wiley, New York, 1951) pp. 359–373.
J. Edmonds and R.M. Karp, “Theoretical improvements in algorithmic efficiency for network flow problems”, Journal of the Association for Computing Machinery 19 (1972) 248–264.
M.L. Fredman, J. Komlós and E. Szemerédi, “Storing a sparse table with O(1) worst case access time”, Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science (1982), 165–169.
M.L. Fredman and R.E. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithms”, preprint, January, 1984.
Z. Galil, S. Micali and H. Gabow, “Maximal weighted matching on general graphs”, Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science (1982), 255–261.
J.E. Hopcraft and R.M. Karp, “A n 5/2 Algorithm for maximum matchings in bipartite graphs”, SIAM Journal on Computing 2 (1973) 225–231.
M.S. Hung, “A polynomial simplex method for the assignment problem”, Operations Research 31 (1983) 595–600.
M.S. Hung and W.O. Rom, “Solving the assignment problem by relaxation”, Operations Research 28 (1980) 969–982.
H.W. Kuhn, “The Hungarian method for the assignment problem”, Naval Research Logistics Quarterly 2 (1955) 83–97.
E. Lawler, Combinatorial optimization, networks and matroids (Holt, Rinehart and Winston, New York, 1976).
E. Roohy-Laleh, Improvements to the theoretical efficiency of the network simplex method , Ph.D. Thesis, Carleton University (Ottawa, 1981).
D.D. Sleator and R.E. Tarjan, “Self-adjusting heaps”, SIAM Journal on Computing , submitted.
R.E. Tarjan, “Amortized computational complexity”, SIAM Journal on Algebraic and Discrete Methods , to appear.
Download references
Author information
Authors and affiliations.
Department of Industrial Engineering and Operations Research, Columbia University, 10027, New York, NY, USA
D. Goldfarb
You can also search for this author in PubMed Google Scholar
Additional information
This research was supported in part by the National Science Foundation under Grant No. MCS-8006064 and by the Army Research Office under Contracts No. DAAG 29-82-K0163 and DAAG 29-83-K0106
Rights and permissions
Reprints and permissions
About this article
Goldfarb, D. Efficient dual simplex algorithms for the assignment problem. Mathematical Programming 33 , 187–203 (1985). https://doi.org/10.1007/BF01582245
Download citation
Received : 31 May 1984
Revised : 02 January 1985
Issue Date : November 1985
DOI : https://doi.org/10.1007/BF01582245
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
- Assignment Problem
- Dual Simplex Method
- Weighted Matching
- Optimization
- Block Pivot
- Find a journal
- Publish with us
- Track your research
IMAGES
COMMENTS
We study algorithms that produce iterates according to well determined rules–Deterministic Algorithm rather than some random selection process–Randomized Algorithm.
assignment problem. The approximation methods considered and defined in Section 2 are termed (1) the suboptimization method, (2) the row/column-scan method, and (3) the matrix-scan method. Definition of these methods is pre- ceded by the results of a timing study of an exact assignment algorithm.
While it is possible to solve any of these problems using the simplex algorithm, or in worst-case polynomial time using the ellipsoid method, each specialization has a smaller solution space and thus more efficient algorithms designed to take advantage of its special structure.
Simplex Algorithm adapted to solve network problems. The Simplex Algorithm is a general purpose algorithm to find the maximum/minimum of a linear cost function with linear constraints. Linear program that are formulated from network flow problems often have a special structure.
Identify and set up a linear program in standard maximization form. Convert inequality constraints to equations using slack variables. Set up the initial simplex tableau using the objective function and slack equations. Find the optimal simplex tableau by performing pivoting operations.
This particular class of transportation problems is called the assignment problems. These problems can, of course, be solved by the streamlined Simplex algorithm.
In this chapter, you will: Investigate real world applications of linear programming and related methods. Solve linear programming maximization problems using the simplex method. Solve linear programming minimization problems using the simplex method. Thumbnail: Polyhedron of simplex algorithm in 3D.
In this section, you will learn to solve linear programming minimization problems using the simplex method. Identify and set up a linear program in standard minimization form; Formulate a dual problem in standard maximization form; Use the simplex method to solve the dual maximization problem
Efficient algorithms based upon Balinski's signature method are described for solving then × n assignment problem. These algorithms are special variants of the dual simplex method and are shown to have computational bounds of O(n 3).
1 Introduction. We will now discuss the best-known algorithm (really, a family of algorithms) for solving a linear program, the simplex algorithm. We will demonstrate it on an example. Consider again the linear program for our (unmodi ed) painting example: maximize 3x1 + 2x2 subject to 4x1 + 2x2 16 x1 + 2x2 8 x1 + x2. 5. x2 0; x1 0.