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

Link

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

Cited from

economics_finance, operations_research

Cited by

3 citations across 3 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.

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

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)

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:8edafb1ae636 · see in the full table