50 Years of Integer Programming 1958-2008 pp 29–47 Cite as
The Hungarian Method for the Assignment Problem
- Harold W. Kuhn 9
- First Online: 01 January 2009
8957 Accesses
185 Citations
8 Altmetric
This paper has always been one of my favorite “children,” combining as it does elements of the duality of linear programming and combinatorial tools from graph theory. It may be of some interest to tell the story of its origin.
- Graph Theory
- Combinatorial Optimization
- Integer Program
- Assignment Problem
- National Bureau
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
This is a preview of subscription content, access via your institution .
Buying options
- Available as PDF
- Read on any device
- Instant download
- Own it forever
- Compact, lightweight edition
- Dispatched in 3 to 5 business days
- Free shipping worldwide - see info
Tax calculation will be finalised at checkout
Purchases are for personal use only
Unable to display preview. Download preview PDF.
H.W. Kuhn, On the origin of the Hungarian Method , History of mathematical programming; a collection of personal reminiscences (J.K. Lenstra, A.H.G. Rinnooy Kan, and A. Schrijver, eds.), North Holland, Amsterdam, 1991, pp. 77–81.
Google Scholar
A. Schrijver, Combinatorial optimization: polyhedra and efficiency , Vol. A. Paths, Flows, Matchings, Springer, Berlin, 2003.
MATH Google Scholar
Download references
Author information
Authors and affiliations.
Princeton University, Princeton, USA
Harold W. Kuhn
You can also search for this author in PubMed Google Scholar
Corresponding author
Correspondence to Harold W. Kuhn .
Editor information
Editors and affiliations.
Inst. Informatik, Universität Köln, Pohligstr. 1, Köln, 50969, Germany
Michael Jünger
Fac. Sciences de Base (FSB), Ecole Polytechnique Fédérale de Lausanne, Lausanne, 1015, Switzerland
Thomas M. Liebling
Ensimag, Institut Polytechnique de Grenoble, avenue Félix Viallet 46, Grenoble CX 1, 38031, France
Denis Naddef
School of Industrial &, Georgia Institute of Technology, Ferst Drive NW., 765, Atlanta, 30332-0205, USA
George L. Nemhauser
IBM Corporation, Route 100 294, Somers, 10589, USA
William R. Pulleyblank
Inst. Informatik, Universität Heidelberg, Im Neuenheimer Feld 326, Heidelberg, 69120, Germany
Gerhard Reinelt
ed Informatica, CNR - Ist. Analisi dei Sistemi, Viale Manzoni 30, Roma, 00185, Italy
Giovanni Rinaldi
Center for Operations Reserach &, Université Catholique de Louvain, voie du Roman Pays 34, Leuven, 1348, Belgium
Laurence A. Wolsey
Rights and permissions
Reprints and Permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter.
Kuhn, H.W. (2010). The Hungarian Method for the Assignment Problem. In: Jünger, M., et al. 50 Years of Integer Programming 1958-2008. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-68279-0_2
Download citation
DOI : https://doi.org/10.1007/978-3-540-68279-0_2
Published : 06 November 2009
Publisher Name : Springer, Berlin, Heidelberg
Print ISBN : 978-3-540-68274-5
Online ISBN : 978-3-540-68279-0
eBook Packages : Mathematics and Statistics Mathematics and Statistics (R0)
Share this chapter
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
- Find a journal
- Publish with us
- Home
- Article citations
- Biomedical & Life Sci.
- Business & Economics
- Chemistry & Materials Sci.
- Computer Sci. & Commun.
- Earth & Environmental Sci.
- Engineering
- Medicine & Healthcare
- Physics & Mathematics
- Social Sci. & Humanities
Journals by Subject
- Biomedical & Life Sciences
- Chemistry & Materials Science
- Computer Science & Communications
- Earth & Environmental Sciences
- Social Sciences & Humanities
- Paper Submission
- Information for Authors
- Peer-Review Resources
- Open Special Issues
- Open Access Statement
- Frequently Asked Questions
Publish with us
Article citations more>>.
Kuhn, H.W. (1955) The Hungarian Method for the Assignment Problem. Naval Research Logistics Quarterly, 5, 83- 97. http://dx.doi.org/10.1002/nav.3800020109
has been cited by the following article:
TITLE: Solving the Unbalanced Assignment Problem: Simpler Is Better
KEYWORDS: Assignment Problem , Hungarian Method , Textbook Formulation
JOURNAL NAME: American Journal of Operations Research , Vol.6 No.4 , June 30, 2016
ABSTRACT: Recently, Yadaiah and Haragopal published in the American Journal of Operations Research a new approach to solving the unbalanced assignment problem. They also provide a numerical example which they solve with their approach and get a cost of 1550 which they claim is optimum. This approach might be of interest; however, their approach does not guarantee the optimal solution. In this short paper, we will show that solving this same example from the Yadaiah and Haragopal paper by using a simple textbook formulation to balance the problem and then solve it with the classic Hungarian method of Kuhn yields the true optimal solution with a cost of 1520.
Related Articles:
- Open Access Articles The Paired Assignment Problem Vardges Melkonian Open Journal of Discrete Mathematics Vol.4 No.2 , April 23, 2014 DOI: 10.4236/ojdm.2014.42007
- Open Access Articles Research on Location-Routing Problem with Empirical Analysis for Regional Logistics Distribution Qian Zhang Applied Mathematics Vol.5 No.15 , August 14, 2014 DOI: 10.4236/am.2014.515224
- Open Access Articles An Application of the Hungarian Algorithm to Solve Traveling Salesman Problem Janusz Czopik American Journal of Computational Mathematics Vol.9 No.2 , June 11, 2019 DOI: 10.4236/ajcm.2019.92005
- Open Access Articles ACGA Algorithm of Solving Weapon - Target Assignment Problem Jiuyong Zhang, Xiaojing Wang, Chuanqing Xu, Dehui Yuan Open Journal of Applied Sciences Vol.2 No.4B , January 14, 2013 DOI: 10.4236/ojapps.2012.24B018
- Open Access Articles Solving the Unbalanced Assignment Problem: Simpler Is Better Nathan Betts, Francis J. Vasko American Journal of Operations Research Vol.6 No.4 , June 30, 2016 DOI: 10.4236/ajor.2016.64028
- Journals A-Z
About SCIRP
- Publication Fees
- For Authors
- Peer-Review Issues
- Special Issues
- Manuscript Tracking System
- Subscription
- Translation & Proofreading
- Volume & Issue
- Open Access
- Publication Ethics
- Preservation
- Privacy Policy
The blue social bookmark and publication sharing system.
Log in with your username.
I've lost my password.
Log in with your OpenID-Provider.
- Other OpenID-Provider
- The Hungarian Method f...
Publication title
copy delete add this publication to your clipboard community post history of this post URL DOI BibTeX EndNote APA Chicago DIN 1505 Harvard MSOffice XML The Hungarian Method for the Assignment Problem
H. Kuhn . Naval Research Logistics Quarterly 2 (1--2): 83--97 ( March 1955 )
Links and resources
Comments and reviews (0), cite this publication.
- MSOffice XML
- all formats
- Last update 12 years ago
- Created 12 years ago
In collection of:
Tags ( @gergie 's tags highlighted).
- jabref:nokeywordassigned
BibSonomy is offered by the KDE group of the University of Kassel, the DMIR group of the University of Würzburg, and the L3S Research Center , Germany.
Academia.edu no longer supports Internet Explorer.
To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to upgrade your browser .
Enter the email address you signed up with and we'll email you a reset link.
- We're Hiring!
- Help Center
The Hungarian Method for the Assignment Problem Introduction by
This paper has always been one of my favorite "children," combining as it does elements of the duality of linear programming and combinatorial tools from graph theory. It may be of some interest to tell the story of its origin.
Related Papers
Jeff Erickson
Historia Mathematica
Tinne Hoff Kjeldsen
Linear Programming 1
Joel Padilla
Dantzing et al (1997)
Thu Hiền Chu Thị
Proceedings of the 3rd workshop on Biologically …
Simone Ludwig
European Journal of Operational Research
Kurt Jörnsten
Archive For History of Exact Sciences
Trends in Applied Intelligent Systems, Proceedings of the 23rd Int. Conf. on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2010, Cordoba, Spain, June 1-4, 2010. Garcìa-Pedrajas, N. et al. (Eds.), LNCS
Stefano Giordani , Marin Lujak
In this work we address the Multi-Robot Task Allocation Problem (MRTA). We assume that the decision making environment is decentralized with as many decision makers (agents) as the robots in the system. To solve this problem, we developed a distributed version of the Hungarian Method for the assignment problem. The robots autonomously perform different substeps of the Hungarian algorithm on the base of the individual and the information received through the messages from the other robots in the system. It is assumed that each robot agent has an information regarding its distance from the targets in the environment. The inter-robot communication is performed over a connected dynamic communication network and the solution to the assignment problem is reached without any common coordinator or a shared memory of the system. The algorithm comes up with a global optimum solution in O(n3) cumulative time (O(n2) for each robot), with O(n3) number of messages exchanged among the n robots.
Jahresbericht der Deutschen Mathematiker-Vereinigung
Raymond Hemmecke
Nature and Biologically Inspired …
RELATED PAPERS
IJAR Indexing
Gunduz Ulusoy
Mathematics and War
alejandro garcia
Boletín de la Sociedad Matemática Mexicana
Carlos Valencia
Journal of Combinatorial Optimization
Karine Deschinkel
Peter Sudhölter , T. Raghavan
Herman van Dijk
Discrete Applied Mathematics
Mauro Dell'Amico
Tamás Terlaky
Panos M Pardalos
Mathematical Intelligencer
fatima khlifa
The Mathematical Intelligencer
Tigranuhy Grigoryan
Naval Research Logistics
Dimitris Alevras
Jacques Desrosiers
Journal of Combinatorial Theory, Series B
Judith Keijsper
Alexandre Ribeiro
Industrial Robot: An …
Graham Purnell , Helge A Wurdemann
Christian Magnanti
Discrete Optimization
Craig Tovey
Interational Journal of Operations Research
Computers & Industrial Engineering
Electronic Notes in Discrete Mathematics
Viet Nguyen
RAM BILAS MISRA
Andrea Lodi
Tania Querido , Nair de Abreu , Paulo Boaventura Netto
Operations Research Letters
Vangelis Th. Paschos
International Journal of Operations Reseach
Theory and Decision
Gianfranco Gambarelli
Tomasz Kuszewski
Scholarly Journal of Mathematics & Science
Dama Academic Scholarly & Scientific Research Society
Stan Van Hoesel
Cornelis Roos
RELATED TOPICS
- We're Hiring!
- Help Center
- Find new research papers in:
- Health Sciences
- Earth Sciences
- Cognitive Science
- Mathematics
- Computer Science
- Academia ©2023
IMAGES
VIDEO
COMMENTS
In math, a computation method is used to find an answer in regards to any given problem. The most common computation methods make up the majority of basic math functions including addition, subtraction, multiplication and division.
Are you facing issues with the sound on your computer? Having audio problems can be frustrating, especially if you rely on your computer for work or entertainment. But don’t worry, there are several effective methods you can try to fix the ...
According to StateUniversity.com, the project method of teaching is an educational enterprise in which children solve a particular problem over a period of days or weeks. It offers teachers a way to develop in-depth thinking in young childr...
Thus, although there is a transfer. Page 3. H. W. KUHN. 85 possible in this optimal assignment (move 1 from job 1 to job 2), it leads to a complete assign- ment
Assuming that numerical scores are available for the performance of each of n persons on each of n jobs, the “assignment problem” is the quest for an
H.W. Kuhn, On the origin of the Hungarian Method, History of mathematical programming; a collection of personal reminiscences (J.K. Lenstra, A.H.G. Rinnooy Kan
The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal–dual
H. Kuhn · Published 1 March 1955 · Economics · Naval Research Logistics (NRL).
The authors have proposed a heuristic method for solving assignment problems with less computing time in comparison with Hungarian algorithm that gives
To establish a clear relationship between clusters and words, we employ the maximum Hungarian matching technique (Kuhn 1955 ) on a bipartite graph, using the
Kuhn, H.W. (1955) The Hungarian Method for the Assignment Problem. Naval Research Logistics Quarterly, 5, 83- 97.
The Hungarian Method for the Assignment Problem. H. Kuhn. Naval Research Logistics Quarterly 2 (1--2): 83--97 (March 1955 ). Links and resources. DOI: 10.1002
This paper has always been one of my favorite "children," combining as it does elements of the duality of linear programming and combinatorial tools from
chapter the hungarian method for the assignment problem harold kuhn introduction harold kuhn this paper has always been one of my favorite combining as it.