×
Akgül, Mustafa

A genuinely polynomial primal simplex algorithm for the assignment problem. (English) Zbl 0808.90089

Discrete Appl. Math. 45, No. 2, 93-115 (1993).
The author presents a primal simplex algorithm that solves the assignment problem in \(O(n^ 2)\) pivot operations. The algorithm works with an increasing sequence of subgraphs. A feasible basis corresponds to a strongly feasible tree. Degeneration is dealt with Dantzig’s rule. The total number of consecutive degenerate pivots is bounded by \({1\over 2}(n+ 2)(n- 1)\). The total number of nondegenerate pivots is bounded by \(n-1\). An update of the basis and dual variables can be performed in \(O(n)\) operations.
The paper contains a short characterization of other primal or dual simplex algorithms for the assignment problem.
Reviewer: J.Terno (Dresden)

Cited in 11 Documents

MSC:

90C05 Linear programming
90B80 Discrete location and assignment
90C35 Programming involving graphs or networks

Keywords:

network simplex method; polynomial algorithms; primal simplex algorithm; assignment problem; increasing sequence of subgraphs
Cite Review PDF
Full Text: DOI

References:

[1] Achatz, H.; Kleinschmidt, P.; Paparrizos, K., A dual forest algorithm for the assignment problem, Tech. Rept. (1989), Universität Passau
[2] Akgül, M., Topics in Relaxation and Ellipsoidal Methods, Research Notes in Mathematics, 97 (1984), Pitman: Pitman London · Zbl 0549.90061
[3] Akgül, M., Working Paper IEOR 87-07 (1987), Bilkent University: Bilkent University Ankara, also · Zbl 0808.90089
[4] Akgül, M., A sequential dual simplex algorithm for the linear assignment problem, Oper. Res. Lett., 7, 155-158 (1988) · Zbl 0654.90053
[5] Akgül, M., Shortest paths and the simplex method, Working Paper IEOR 88-04 (1988), Bilkent University: Bilkent University Ankara
[6] Akgül, M.; Ekin, O., A dual feasible forest algorithm for the linear assignment problem, Res. Opér., 25, 403-411 (1991) · Zbl 0744.90088
[7] Ali, A. I.; Helgason, R. V.; Kennington, J. L.; Lall, H. S., Primal simplex network codes: state-of-the-art implementation technology, Networks, 8, 315-339 (1978)
[8] Balinski, M. L., Presented at Mathematical Programming Symposium, Bonn (1982), also · Zbl 0583.90064
[9] Balinski, M. L., A competitive (dual) simplex method for the assignment problem, Math. Programming, 34, 125-141 (1986) · Zbl 0596.90064
[10] Balinski, M. L.; Gomory, R. E., A primal method for the assignment and transportation problems, Management Sci., 10, 578-598 (1964)
[11] Barr, R. S.; Glover, F.; Klingman, D., The alternating basis algorithm for assignment problems, Math. Programming, 13, 1-13 (1977) · Zbl 0378.90097
[12] Bertsekas, D., A new algorithm for the assignment problem, Math. Programming, 21, 152-157 (1981) · Zbl 0461.90069
[13] Bixby, R. B., Matroids and operations research, (Greenberg, H. J., Advanced Techniques in the Practice of Operations Research (1982), North-Holland: North-Holland Amsterdam), 333-459
[14] Bradley, G. H.; Brown, G. G.; Graves, G. W., Design and implementation of large scale primal transshipment algorithms, Management Sci., 24, 1-34 (1977) · Zbl 0373.90079
[15] Burkard, R. E., Travelling salesman and assignment problems: a survey, (Annals of Discrete Mathematics, 4 (1979), North-Holland: North-Holland Amsterdam), 193-215 · Zbl 0409.05041
[16] Burkard, R. E.; Hahn, W.; Zimmerman, W., An algebraic approach to assignment problems, Math. Programming, 12, 318-327 (1977) · Zbl 0361.90047
[17] Carpaneto, G.; Toth, P., Primal-dual algorithms for the assignment problem, Discrete Appl. Math., 18, 137-153 (1987) · Zbl 0632.90041
[18] Chvátal, V., Linear Programming (1983), Freeman: Freeman San Francisco, CA · Zbl 0318.05002
[19] Cunningham, W. H., A network simplex method, Math. Programming, 11, 105-116 (1976) · Zbl 0352.90039
[20] Cunningham, W. H., Theoretical properties of the network simplex method, Math. Oper. Res., 4, 196-208 (1979) · Zbl 0412.90068
[21] Cunningham, W. H.; Marsh, A. B., A primal algorithm for optimum matching, Math. Programming Stud., 8, 50-72 (1978) · Zbl 0409.90081
[22] Dantzig, G. B., Linear Programming and Extensions (1963), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0108.33103
[23] Derigs, U., The shortest augmenting path method for solving assignment problems—motivation and computational experience, Ann. Oper. Res., 4, 57-102 (1985), 1986
[24] Dinic, E. A.; Kronrad, M. A., An algorithm for the solution of the assignment problem, Soviet Math. Dokl., 10, 1324-1326 (1969) · Zbl 0213.44801
[25] Edmonds, J.; Karp, R. M., Theoretical improvements in algorithmic efficiency for network flow problems, J. ACM, 19, 248-264 (1972) · Zbl 0318.90024
[26] Ford, L. R.; Fulkerson, D. R., Flows in Networks (1962), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0139.13701
[27] Fredman, M. L.; Tarjan, R. E., Proceedings 25th FOCS, 338-346 (1984), also in
[28] Glover, F.; Karney, D., Implementation and computational comparisons of primal, dual, primal-dual codes for minimum cost network flow problems, Networks, 4, 191-212 (1977) · Zbl 0282.68020
[29] Goldfarb, D., Efficient dual simplex algorithms for the assignment problem, Math. Programming, 37, 187-203 (1985) · Zbl 0578.90051
[30] Hung, M. S., A polynomial simplex method for the assignment problem, Oper. Res., 31, 595-600 (1983) · Zbl 0519.90056
[31] Hung, M. S.; Rom, W. O., Solving the assignment problem by relaxation, Oper. Res., 27, 969-982 (1980) · Zbl 0441.90062
[32] Johnson, E. L., Flows in networks, (Moder, J. J.; Elmaghraby, S. E., Handbook of Operations Research (1978), Van Nostrand Reinhold: Van Nostrand Reinhold Princeton, NJ) · Zbl 0183.23201
[33] Jonker, R.; Volgenant, A., A shortest path algorithm for dense and sparse linear assignment problems, Computing, 38, 325-340 (1987) · Zbl 0607.90056
[34] Kuhn, H. W., The hungarian method for the assignment problem, Naval Res. Logist. Quart., 2, 83-97 (1955) · Zbl 0143.41905
[35] Munkres, J., Algorithms for the assignment and transportation problems, SIAM J. Comput., 5, 32-38 (1957) · Zbl 0083.15302
[36] Orlin, J. B., On the simplex algorithm for networks and generalized networks, Math. Programming Stud., 24, 166-178 (1985) · Zbl 0592.90031
[37] Papadimitriou, C.; Steiglitz, K., Combinatorial Optimization: Algorithms & Complexity (1982), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0503.90060
[38] Rockafellar, R. T., Network Flows and Monotropic Optimization (1984), Wiley: Wiley New York · Zbl 0596.90055
[39] Roohy-Laleh, Dissertation Abstract International, 43, 448B (1982), also
[40] Sleator, D. D.; Tarjan, R. E., A data structure for dynamic trees, J. Comput. System Sci., 26, 362-391 (1983) · Zbl 0509.68058
[41] Srinivasan, V.; Thompson, G. L., Accelerated algorithms for labelling and relabelling of trees, with applications to distribution problems, J. ACM, 19, 712-726 (1972) · Zbl 0255.90071
[42] Srinivasan, V.; Thompson, G. L., Benefit-cost analysis for coding techniques for the primal transportation problem, J. ACM, 20, 184-213 (1973) · Zbl 0257.68034
[43] Srinivasan, V.; Thompson, G. L., Cost operator algorithms for the transportation problem, Math. Programming, 12, 372-391 (1977) · Zbl 0362.90058
[44] Tarjan, R. E., Data Structures and Network Algorithms (1983), SIAM: SIAM Philadelphia, PA · Zbl 0584.68077
[45] Thompson, G. L., A recursive method for the assignment problems, (Annals of Discrete Mathematics, 11 (1981), North-Holland: North-Holland Amsterdam), 319-343 · Zbl 0469.90051
[46] Tomizawa, N., On some techniques useful for solution of transportation network problems, Networks, 1, 173-194 (1972) · Zbl 0253.90015
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.