The assignment problem revisited
- Original Paper
- Published: 16 August 2021
- Volume 16 , pages 1531–1548, ( 2022 )
Cite this article
- Carlos A. Alfaro ORCID: orcid.org/0000-0001-9783-8587 1 ,
- Sergio L. Perez 2 ,
- Carlos E. Valencia 3 &
- Marcos C. Vargas 1
937 Accesses
4 Citations
4 Altmetric
Explore all metrics
First, we give a detailed review of two algorithms that solve the minimization case of the assignment problem, the Bertsekas auction algorithm and the Goldberg & Kennedy algorithm. It was previously alluded that both algorithms are equivalent. We give a detailed proof that these algorithms are equivalent. Also, we perform experimental results comparing the performance of three algorithms for the assignment problem: the \(\epsilon \) - scaling auction algorithm , the Hungarian algorithm and the FlowAssign algorithm . The experiment shows that the auction algorithm still performs and scales better in practice than the other algorithms which are harder to implement and have better theoretical time complexity.
This is a preview of subscription content, log in via an institution to check access.
Access this article
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
Some results on an assignment problem variant
Pritibhushan Sinha
Integer Programming
A Full Description of Polytopes Related to the Index of the Lowest Nonzero Row of an Assignment Matrix
Bertsekas, D.P.: The auction algorithm: a distributed relaxation method for the assignment problem. Annal Op. Res. 14 , 105–123 (1988)
Article MathSciNet Google Scholar
Bertsekas, D.P., Castañon, D.A.: Parallel synchronous and asynchronous implementations of the auction algorithm. Parallel Comput. 17 , 707–732 (1991)
Article Google Scholar
Bertsekas, D.P.: Linear network optimization: algorithms and codes. MIT Press, Cambridge, MA (1991)
MATH Google Scholar
Bertsekas, D.P.: The auction algorithm for shortest paths. SIAM J. Optim. 1 , 425–477 (1991)
Bertsekas, D.P.: Auction algorithms for network flow problems: a tutorial introduction. Comput. Optim. Appl. 1 , 7–66 (1992)
Bertsekas, D.P., Castañon, D.A., Tsaknakis, H.: Reverse auction and the solution of inequality constrained assignment problems. SIAM J. Optim. 3 , 268–299 (1993)
Bertsekas, D.P., Eckstein, J.: Dual coordinate step methods for linear network flow problems. Math. Progr., Ser. B 42 , 203–243 (1988)
Bertsimas, D., Tsitsiklis, J.N.: Introduction to linear optimization. Athena Scientific, Belmont, MA (1997)
Google Scholar
Burkard, R., Dell’Amico, M., Martello, S.: Assignment Problems. Revised reprint. SIAM, Philadelphia, PA (2011)
Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for network problems. SIAM J. Comput. 18 (5), 1013–1036 (1989)
Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum flow problem. J. Assoc. Comput. Mach. 35 , 921–940 (1988)
Goldberg, A.V., Tarjan, R.E.: Finding minimum-cost circulations by successive approximation. Math. Op. Res. 15 , 430–466 (1990)
Goldberg, A.V., Kennedy, R.: An efficient cost scaling algorithm for the assignment problem. Math. Programm. 71 , 153–177 (1995)
MathSciNet MATH Google Scholar
Goldberg, A.V., Kennedy, R.: Global price updates help. SIAM J. Discr. Math. 10 (4), 551–572 (1997)
Kuhn, H.W.: The Hungarian method for the assignment problem. Naval Res. Logist. Quart. 2 , 83–97 (1955)
Kuhn, H.W.: Variants of the Hungarian method for the assignment problem. Naval Res. Logist. Quart. 2 , 253–258 (1956)
Lawler, E.L.: Combinatorial optimization: networks and matroids, Holt. Rinehart & Winston, New York (1976)
Orlin, J.B., Ahuja, R.K.: New scaling algorithms for the assignment ad minimum mean cycle problems. Math. Programm. 54 , 41–56 (1992)
Ramshaw, L., Tarjan, R.E., Weight-Scaling Algorithm, A., for Min-Cost Imperfect Matchings in Bipartite Graphs, : IEEE 53rd Annual Symposium on Foundations of Computer Science. New Brunswick, NJ 2012 , 581–590 (2012)
Zaki, H.: A comparison of two algorithms for the assignment problem. Comput. Optim. Appl. 4 , 23–45 (1995)
Download references
Acknowledgements
This research was partially supported by SNI and CONACyT.
Author information
Authors and affiliations.
Banco de México, Mexico City, Mexico
Carlos A. Alfaro & Marcos C. Vargas
Mountain View, CA, 94043, USA
Sergio L. Perez
Departamento de Matemáticas, CINVESTAV del IPN, Apartado postal 14-740, 07000, Mexico City, Mexico
Carlos E. Valencia
You can also search for this author in PubMed Google Scholar
Corresponding author
Correspondence to Carlos A. Alfaro .
Ethics declarations
Conflict of interest.
There is no conflict of interest.
Additional information
Publisher's note.
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The authors were partially supported by SNI and CONACyT.
Rights and permissions
Reprints and permissions
About this article
Alfaro, C.A., Perez, S.L., Valencia, C.E. et al. The assignment problem revisited. Optim Lett 16 , 1531–1548 (2022). https://doi.org/10.1007/s11590-021-01791-4
Download citation
Received : 26 March 2020
Accepted : 03 August 2021
Published : 16 August 2021
Issue Date : June 2022
DOI : https://doi.org/10.1007/s11590-021-01791-4
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
- Bertsekas auction algorithm
- Combinatorial optimization and matching
- Find a journal
- Publish with us
- Track your research
IMAGES
VIDEO
COMMENTS
Following steps are involved in solving this Assignment problem, 1. Locate the smallest cost element in each row of the given cost table starting with the first row. Now, this smallest element is subtracted form each element of that row. So, we will be getting at least one zero in each row of this new table.
In this step, we will solve the LP problem by calling solve () method. We can print the final value by using the following for loop. From the above results, we can infer that Worker-1 will be assigned to Job-1, Worker-2 will be assigned to job-3, Worker-3 will be assigned to Job-2, and Worker-4 will assign with job-4.
The assignment problem can be modeled as a linear program, with the property that its associated polyhedron has all the vertices integer valued. Therefore, this problem can be solved using general linear programming techniques. The problem with these techniques is that they do not perform well in practice.