The Hungarian Method for the Assignment Problem

Kuhn, H. W. (1955). The Hungarian Method for the Assignment Problem. Naval Research Logistics Quarterly, 2(1–2), 1-2.

Type

Journal article

Intellectual base

Primary research

Year

1955

Volume

2

Issue

1–2

Pages

1-2

DOI

10.1002/nav.3800020109

DOI registrant

Wiley

Link

https://doi.org/10.1002/nav.3800020109

Cited from

economics_finance, operations_research

Cited by

6 citations across 6 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Network Flow Models
  • the assignment problem was studied by Kuhn (1955), producing the Hungarian algorithm;

    This sourceOriginal polynomial-time algorithm for the maximum-weight bipartite assignment problem; the weighted-assignment cousin of stable matching underlying ad allocation, task scheduling, and real-time dispatch.

    SupportedVerified against the publisher's abstract

    Kuhn states the problem in his own terms, as “the quest for an assignment of persons to jobs so that the sum of the n scores so obtained is as large as possible”, and presents the paper's result as “a new method of solving this problem”. The work therefore supplies both the assignment problem the sentence names and the method the sentence credits to it. The name Hungarian rests on the work's title; the underlying ideas are attributed only to “two Hungarian mathematicians”, and the work does not frame the method in terms of network flow.

    “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.”

    Read by an automated reader; not a human review. How support was checked

• Two-Sided Matching
  • Computer science & operations research: The stable-marriage problem and bipartite assignment underlie online ad-slot allocation, distributed task scheduling, content-delivery routing, and ride-hailing dispatch, where riders and drivers must be paired in real time under mutual constraints rather than by a posted price.

    This sourceOriginal polynomial-time algorithm for the maximum-weight bipartite assignment problem; the weighted-assignment cousin of stable matching underlying ad allocation, task scheduling, and real-time dispatch.

    Supported in partVerified against the publisher's abstract

    Backs only the assignment-algorithm half: it defines the maximum-sum bipartite assignment problem and gives the Hungarian solution method, and says nothing about ad slots, scheduling, routing, dispatch, or stable marriage.

    “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.”

    Read by an automated reader; not a human review. How support was checked

Domain-specific

• Matching
  • For bipartite weighted matching — assigning a cost \(w(e)\) to each edge and minimizing total cost over perfect matchings — the Hungarian algorithm originates with Kuhn (1955) and Munkres (1957), whose own analyses of the method run in \(O(n^4)\) on an \(n \times n\) cost matrix; the \(O(n^3)\) formulation and the reduction to maximum-flow machinery came later, with Tomizawa (1971) and Edmonds–Karp (1972)

Mechanisms

• Assignment Model
  • Solving it is the classic assignment problem, addressed for small instances by the Hungarian algorithm

    This sourceFormulates the classical assignment problem as matching people to jobs to optimize the total score and presents the Hungarian method as a solution.

• Assignment Optimization Matcher
  • This is the classic assignment problem, and its exact solution is well understood.

    This sourceDefines the assignment problem of assigning persons to jobs to maximize total score and presents the Hungarian method for solving it.

• Greedy Assignment Pass
  • The optimum here is a solved, polynomial computation (the Hungarian / Kuhn–Munkres algorithm)

Verification

Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.

Does it back the claim? Read against the text for 2 of 6 citations: 1 supported, 1 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.

Was it audited? Yes. A second, independent pass read the citation against the article text and recorded a verdict.

Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.

See how references were verified.

Registry ID ref:b7f53ef0fb88 · see in the full table