Efficient dual simplex algorithms for the assignment problem. (English) Zbl 0578.90051

Goldfarb, D.

Math. Program. 33, 187-203 (1985).

Algorithms for solving the \(n\times n\) assignment problem are considered. Some modification of Balinski’s method is proposed making it a particular case of the dual simplex method of type \(O(n^ 3)\). In the case of m admissible assignments its realization requires O(m) storage and needs at most \(O(mn+n^ 2\log n)\) computational time. A detailed implementation analysis is also given.

Reviewer: W.Stanczak

MSC:

90C05	Linear programming
68Q25	Analysis of algorithms and problem complexity
65K05	Numerical mathematical programming methods
90B10	Deterministic network models in operations research
68R10	Graph theory (including graph drawing) in computer science
05C35	Extremal problems in graph theory

Keywords:

weighted matching; block-pivot; assignment problem; dual simplex method; implementation analysis

References:

[1]	A.V. Aho, J.E. Hopcroft and J.D. Ullman,The design and analysis of computer algorithms (Addison-Wesley, Reading, MA, 1974). · Zbl 0326.68005
[2]	M.L. Balinski, ”Signature methods for the assignment problem”, to appear inOperations Research. · Zbl 0583.90064
[3]	M.L. Balinski and R.E. Gomory, ”A primal method for the assignment and transportation problems”,Management Science 10 (1964) 578–593.
[4]	R. Barr, F. Glover and D. Klingman, ”The alternating path basis algorithm for assignment problems”,Mathematical Programming 13 (1977) 1–13. · Zbl 0378.90097
[5]	D. Bertsekas, ”A new algorithm for the assignment problem”,Mathematical Programming 21 (1981) 152–171. · Zbl 0461.90069
[6]	W.H. Cunningham, ”A network simplex method”,Mathematical Programming 11 (1976) 105–116. · Zbl 0352.90039
[7]	W.H. Cunningham and A.B. Marsh, III, ”A primal algorithm for optimum matching”,Mathematical Programming Study 8 (1978) 50–72. · Zbl 0409.90081
[8]	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.
[9]	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. · Zbl 0318.90024
[10]	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.
[11]	M.L. Fredman and R.E. Tarjan, ”Fibonacci heaps and their uses in improved network optimization algorithms”, preprint, January, 1984.
[12]	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.
[13]	J.E. Hopcraft and R.M. Karp, ”An 5/2 Algorithm for maximum matchings in bipartite graphs”,SIAM Journal on Computing 2 (1973) 225–231. · Zbl 0266.05114
[14]	M.S. Hung, ”A polynomial simplex method for the assignment problem”,Operations Research 31 (1983) 595–600. · Zbl 0519.90056
[15]	M.S. Hung and W.O. Rom, ”Solving the assignment problem by relaxation”,Operations Research 28 (1980) 969–982. · Zbl 0441.90062
[16]	H.W. Kuhn, ”The Hungarian method for the assignment problem”,Naval Research Logistics Quarterly 2 (1955) 83–97. · Zbl 0143.41905
[17]	E. Lawler,Combinatorial optimization, networks and matroids (Holt, Rinehart and Winston, New York, 1976). · Zbl 0413.90040
[18]	E. Roohy-Laleh,Improvements to the theoretical efficiency of the network simplex method, Ph.D. Thesis, Carleton University (Ottawa, 1981).
[19]	D.D. Sleator and R.E. Tarjan, ”Self-adjusting heaps”,SIAM Journal on Computing, submitted. · Zbl 0618.68017
[20]	R.E. Tarjan, ”Amortized computational complexity”,SIAM Journal on Algebraic and Discrete Methods, to appear. · Zbl 0599.68046