• DOI: 10.1007/978-3-540-68279-0_2
  • Corpus ID: 9426884

The Hungarian method for the assignment problem

  • Published in 50 Years of Integer… 1 March 1955

Mathematics

  • Naval Research Logistics (NRL)

11,480 Citations

A note on hungarian method for solving assignment problem, the optimal assignment problem: an investigation into current solutions, new approaches and the doubly stochastic polytope, an effective algorithm to solve assignment problems : opportunity cost approach, optimal assignment problem on record linkage, an application of the hungarian algorithm to solve traveling salesman problem.

  • Highly Influenced

Heuristic algorithms and learning techniques: applications to the graph coloring problem

A simulation of the faculty-assignment problem: an integer programming approach, computational studies of randomized multidimensional assignment problems, optimal solution of an assignment problem as a special case of transportation problem, assignment problems by, 17 references, a combinatorial algorithm, solution of the personnel classification problem with the method of optimal regions, the problem of classification of personnel, history of mathematical programming : a collection of personal reminiscences, on representatives of subsets, on a personnel assignment problem, on the hitchcock distribution problem, 1. a certain zero-sum two-person game equivalent to the optimal assignment problem, über graphen und ihre anwendung auf determinantentheorie und mengenlehre, related papers.

Showing 1 through 3 of 0 Related Papers

     
 








 

, 1955, vol. 2, issue 1‐2, 83-97

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 assignment of persons to jobs so that the sum of the n scores so obtained is as large as possible. It is shown that ideas latent in the work of two Hungarian mathematicians may be exploited to yield a new method of solving this problem.

1955

(137)

(external link)


This item may be available elsewhere in EconPapers: for items with the same title.

BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

for this article

in Naval Research Logistics Quarterly from
Bibliographic data for series maintained by Wiley Content Delivery ( ).

The Hungarian method for the assignment problem

  • Scinapse’s Top 10 Citation Journals & Affiliations graph reveals the quality and authenticity of citations received by a paper.
  • Discover whether citations have been inflated due to self-citations, or if citations include institutional bias.

The Hungarian Method for the Assignment Problem

  • First Online: 01 January 2009

Cite this chapter

the hungarian method for the assignment problem naval research logistics quarterly

  • Harold W. Kuhn 9  

9893 Accesses

188 Citations

11 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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save.

  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
  • 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

Institutional subscriptions

Unable to display preview.  Download preview PDF.

Similar content being viewed by others

the hungarian method for the assignment problem naval research logistics quarterly

On weighted means and their inequalities

the hungarian method for the assignment problem naval research logistics quarterly

Constrained Variational Optimization

the hungarian method for the assignment problem naval research logistics quarterly

The Alternating Least-Squares Algorithm for CDPCA

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

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

  • Publish with us

Policies and ethics

  • Find a journal
  • Track your research

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

paper cover thumbnail

The Hungarian Method for the Assignment Problem Introduction by

Profile image of Nguyễn Hoàng Tín

Related Papers

Discrete Applied Mathematics

the hungarian method for the assignment problem naval research logistics quarterly

Matthew Saltzman

In this essay, we will \discover" the dual problem associated with an LP. We will see how to interpret the meanings of the dual decision variables in the context of the original problem, and we will present some theorems (\facts") about the relationship between the optimal primal and dual solutions that will lead us to the key ideas of the simplex method for solving LPs.

Abstract The theory of duality for linear programs is well-developed and has been successful in advancing both the theory and practice of linear programming. In principle, much of this broad framework can be extended to mixed-integer linear programs, but this has proven difficult, in part because duality theory does not integrate well with current computational practice.

Surveys in Combinatorial Optimization

Mathematical Programming

ELSIE GOTTLIEB

Mathematical …

dulce ponceleon

Vijay Chandru

The theory of flows in networks began to evolve in the early 1950’s.The various linear optimisation questions that could be asked of flows in conserving networks turned out to be neat combinatorial specialisations of linear programming. The simplex method (and its variants) turned out to have very pretty combinatorial interpretations on networks. The algebraic dexterity of linear programming duality led to a unified treatment of many deep theorems in graph theory and combinatorics. In this part, the last of the series on linear programming, we will see glimpses of the theory of network flows through a specific flow optimisation problem — the maximum flow problem.

Springer Optimization and Its Applications

Jean B. Lasserre

Universitext

Dimitris Alevras

American Journal of Applied Mathematics

A.K.M Nazimuddin

Loading Preview

Sorry, preview is currently unavailable. You can download the paper by clicking the button above.

RELATED PAPERS

archana pandey

Mark Karwan

International Journal of Operational Research

Marshal Wang

Kurt Jörnsten

Diego Klabjan

Jacques Desrosiers

Zeitschrift für Operations Research

Endre Boros

Computational Mathematics and Mathematical Physics

Socorro Rangel , Igor Litvinchev

Sublinear Computation Paradigm

kazuhisa makino

Andrew Eberhard

Beitrage Zur Algebra Und Geometrie

Peter McMullen

Thu Hiền Chu Thị

Springer eBooks

Scott Leavengood

Jesper Larsen

Ajit Pal Singh

Trisna Darmawansyah

Vangelis Paschos

Annals of Operations Research

Michael Florian

Mathematics of Operations Research

L. Van Der Heyden

Hussein Ali Hussein Al-Dallal Al-Saeedi

RELATED TOPICS

  •   We're Hiring!
  •   Help Center
  • Find new research papers in:
  • Health Sciences
  • Earth Sciences
  • Cognitive Science
  • Mathematics
  • Computer Science
  • Academia ©2024

Browse Econ Literature

  • Working papers
  • Software components
  • Book chapters
  • JEL classification

More features

  • Subscribe to new research

RePEc Biblio

Author registration.

  • Economics Virtual Seminar Calendar NEW!

IDEAS home

The Hungarian method for the assignment problem

  • Author & abstract
  • 5 Citations
  • Related works & more

Corrections

Suggested citation, download full text from publisher.

Follow serials, authors, keywords & more

Public profiles for Economics researchers

Various research rankings in Economics

RePEc Genealogy

Who was a student of whom, using RePEc

Curated articles & papers on economics topics

Upload your paper to be listed on RePEc and IDEAS

New papers by email

Subscribe to new additions to RePEc

EconAcademics

Blog aggregator for economics research

Cases of plagiarism in Economics

About RePEc

Initiative for open bibliographies in Economics

News about RePEc

Questions about IDEAS and RePEc

RePEc volunteers

Participating archives

Publishers indexing in RePEc

Privacy statement

Found an error or omission?

Opportunities to help RePEc

Get papers listed

Have your research listed on RePEc

Open a RePEc archive

Have your institution's/publisher's output listed on RePEc

Get RePEc data

Use data assembled by RePEc

  • Publication A-Z index
  • Browse by subject

the hungarian method for the assignment problem naval research logistics quarterly

  • Submit Manuscript

the hungarian method for the assignment problem naval research logistics quarterly

Article citations More >>

Kuhn H.W., The Hungarian method for the assignment problem, Naval Research Logistics Quarterly , Vol. 2, 1955, pp. 83-97.

has been cited by the following article:

Progressive Review and Analytical Approach for Optimal Solution of Stochastic Transportation Problems (STP) Involving Multi-Choice Cost

the hungarian method for the assignment problem naval research logistics quarterly

1 Department of Mathematics & Statistics, School of Science & Technology, The University of Fiji, Fiji Islands

2 Vision Institute of Technology, U.P. Technical University, India

3 SUNY, Korea & Ex Vice-Chancellor, Avadh University, India

4 Department of Operations Research, University of Delhi, India

5 Department of Electronics & Communication Engineering Lucknow Institute of Technology, U.P. Technical University, India

  • Conferences
  • Special Issues
  • Google Scholar
  • VIRAL HEPATITIS CONGRESS
  • JournalTOCs

Help & Contacts

  • Questionnaire

Facebook

IMAGES

  1. The Hungarian method for the assignment problem

    the hungarian method for the assignment problem naval research logistics quarterly

  2. How to Solve an Assignment Problem Using the Hungarian Method

    the hungarian method for the assignment problem naval research logistics quarterly

  3. explain the steps in the hungarian method used for solving assignment

    the hungarian method for the assignment problem naval research logistics quarterly

  4. Hungarian Algorithm for Assignment Problem

    the hungarian method for the assignment problem naval research logistics quarterly

  5. explain the steps in the hungarian method used for solving assignment

    the hungarian method for the assignment problem naval research logistics quarterly

  6. Solving the Assignment Problem Using the Hungarian Method

    the hungarian method for the assignment problem naval research logistics quarterly

VIDEO

  1. 2. Minimal Assignment problem {Hungarian Method}

  2. Assignment problem. Hungarian method

  3. 03 Assignment Problem Hungarian Method

  4. Assignment problem Hungarian Method Part1

  5. HUNGARIAN METHOD||ASSIGNMENT PROBLEM ||OPERATIONS RESEARCH|| Lecture

  6. Hungarian Method || Assignment Problem|| Operations Research and Techniques

COMMENTS

  1. The Hungarian method for the assignment problem

    Naval Research Logistics Quarterly. Volume 2, Issue 1-2 p. 83-97. Article. The Hungarian method for the assignment problem ... The preparation of this report was supported, in part, by the ONR Logistics Project, Department of Mathematics, Princeton University. About. PDF. Tools. Request permission; Export citation; Add to favorites;

  2. [PDF] The Hungarian method for the assignment problem

    The Hungarian method for the assignment problem. H. Kuhn. Published in 50 Years of Integer… 1 March 1955. Mathematics. Naval Research Logistics (NRL) This paper has been presented with the Best Paper Award. It will appear in print in Volume 52, No. 1, February 2005. View on Wiley.

  3. PDF The Hungarian method for the assignment problem

    THE HUNGARIAN METHOD FOR THE ASSIGNMENT. PROBLEM'. H. W. Kuhn. Bryn Y a w College. Assuming that numerical scores are available for the perform- ance of each of n persons on each of n jobs, the "assignment problem" is the quest for an assignment of persons to jobs so that the sum of the. n scores so obtained is as large as possible.

  4. PDF Chapter 2 The Hungarian Method for the Assignment Problem

    together, the Hungarian Method was born. I tested the algorithm by solving 12 by 12 problems with random 3-digit ratings by hand. I could do any such problem, with pencil and paper, in no more than 2 hours. This seemed to be much better than any other method known at the time. The paper was published in Naval Research Logistics Quarterly. This ...

  5. The Hungarian method for the assignment problem

    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 assignment of persons to jobs so that the sum of the n scores so obtained is as large as possible.

  6. The Hungarian method for the assignment problem

    The Hungarian method for the assignment problem. H. W. Kuhn. Naval Research Logistics Quarterly, 1955, vol. 2, issue 1‐2, 83-97 . Abstract: 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 assignment of persons to jobs so that the sum of the n scores so obtained is as large as possible.

  7. The Hungarian method for the assignment problem

    Harold W. Kuhn | Naval Research Logistics Quarterly | This paper has always been one of my favorite "children," combining as it does elements of the duali ... The Hungarian method for the assignment problem. Harold W. Kuhn. 17. View details (1 authors) Naval Research Logistics Quarterly. Volume: 2, Issue: 1, Pages: 83 - 97. Published: Mar 1 ...

  8. The Hungarian Method for the Assignment Problem

    The Hungarian Method was initially proposed by Kuhn (1955) to solve the Generalised Assignment Problem (GAP). Similar to the ILP, the HM is able to find an optimal solution to said problem. ...

  9. On Kuhn's Hungarian Method—A tribute from Hungary

    Abstract Harold W. Kuhn, in his celebrated paper entitled "The Hungarian Method for the assignment problem" [Naval Res Logist Quart 2 (1955), 83-97] ... Naval Research Logistics (NRL) Volume 52, Issue 1 p. 2-5. On Kuhn's Hungarian Method—A tribute from Hungary. András Frank,

  10. The Hungarian method for the assignment problem

    H. W. Kuhn, 1955. " The Hungarian method for the assignment problem ," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 2 (1‐2), pages 83-97, March. Downloadable! 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 assignment of ...

  11. The Hungarian Method for the Assignment Problem

    Find a journal Publish with us Track your research Search. Cart. Home. 50 Years of Integer Programming 1958-2008. Chapter. The Hungarian Method for the Assignment Problem. Chapter ... 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 ...

  12. On Kuhn's Hungarian Method—A tribute from Hungary

    Downloadable! Harold W. Kuhn, in his celebrated paper entitled "The Hungarian Method for the assignment problem" [Naval Res Logist Quart 2 (1955), 83-97] described an algorithm for constructing a maximum weight perfect matching in a bipartite graph. In his delightful reminescences ["On the origin of the Hungarian method," History of mathematical programming—a collection of personal ...

  13. On Kuhn's Hungarian Method—A tribute from Hungary

    Abstract. Harold W. Kuhn, in his celebrated paper entitled "The Hungarian Method for the assignment problem" [Naval Res Logist Quart 2 (1955), 83-97] described an algorithm for constructing ...

  14. The Hungarian Method for the Assignment Problem Introduction by

    2 The Hungarian Method for the Assignment Problem 31 32 Harold W. Kuhn The following article originally appeared as: H.W. Kuhn, The Hungarian Method for the Assignment Problem, Naval Research Logistics Quarterly 2 (1955) 83-97. 2 The Hungarian Method for the Assignment Problem 33 34 Harold W. Kuhn 2 The Hungarian Method for the Assignment ...

  15. PDF The Hungarian Method

    The Hungarian method for the assignment problem goes back to Kuhn (1955), who proposed an O(n4) algorithm. The O(n3) version ... Naval Research Logistics Quarterly, 2(1-2):83-97, 1955. Nobuaki Tomizawa. On some techniques useful for solution of trans-portation network problems. Networks, 1(2):173-194, 1971.

  16. Naval Research Logistics Quarterly

    Naval Research Logistics Quarterly. Volume 3, Issue 4 p. 253-258. Article. Variants of the hungarian method for assignment problems ...

  17. The Hungarian method for the assignment problem

    H. W. Kuhn, 2005. "The Hungarian method for the assignment problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(1 ... "Single‐machine scheduling with deadlines to minimize the total weighted late work," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(7), pages 582-595, October. More about this item Statistics Access ...

  18. Hungarian algorithm

    The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal-dual methods.It was developed and published in 1955 by Harold Kuhn, who gave it the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians, Dénes Kőnig and Jenő Egerváry.

  19. Kuhn The Hungarian Method for the Assignment

    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 ... The paper was published in Naval Research Logistics Quarterly. This was a nat- ural choice since the project in Game Theory, Linear and Nonlinear Programming, and Combinatorics at ...

  20. (PDF) Development of an accelerating hungarian method for assignment

    Abstract and Figures. The Hungarian method is a well-known method for solving the assignment problem. This method was developed and published in 1955. It was named the Hungarian method because two ...

  21. The Hungarian method for the assignment problem

    Naval Research Logistics (NRL) Volume 52, Issue 1 p. 7-21. The Hungarian method for the assignment problem. H. W. Kuhn, H. W. Kuhn. Search for more papers by this author. H. W. Kuhn, H. W. Kuhn. Search for more papers by this author. ... Wiley Research DE&I Statement and Publishing Policies; Developing World Access; Help & Support.

  22. Kuhn H.W., The Hungarian method for the assignment problem, Naval

    The Hungarian method for the assignment problem, Naval Research Logistics Quarterly, Vol. 2, 1955, pp. 83-97. ... has been reviewed in the light of progressive research works of previous noteworthy researchers. In addition, an analytical approach for the optimal solution (OS) of the proposed stochastic transportation problem has been ...

  23. Naval Research Logistics Quarterly

    Naval Research Logistics Quarterly. Volume 3, Issue 4 p. 253-258. Article. Variants of the hungarian method for assignment problems ...