{ "id": "epd550wjsf", "slug": "assignment-algorithm", "title": "Assignment algorithm", "updated": "2026-09-30", "topic_path": [ { "id": "physical", "label": "Physical world and mathematics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical" }, { "id": "physical.math", "label": "Mathematics and statistics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math" }, { "id": "physical.math.discrete", "label": "Logic and discrete mathematics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.discrete" }, { "id": "physical.math.discrete.discrete", "label": "General discrete mathematics and discrete structures", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.discrete.discrete" }, { "id": "physical.math.discrete.discrete.combinatorics", "label": "Combinatorics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.discrete.discrete.combinatorics" } ], "geo": [ { "id": "geo.nongeo.t1946.physical.math.discrete", "label": "Non-geographic · 1946 to 2000: Logic and discrete mathematics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math.discrete", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1946", "label": "Non-geographic · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946" }, { "id": "geo.nongeo.t1946.physical", "label": "Physical world and mathematics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical" }, { "id": "geo.nongeo.t1946.physical.math", "label": "Mathematics and statistics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math" }, { "id": "geo.nongeo.t1946.physical.math.discrete", "label": "Logic and discrete mathematics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math.discrete" } ] } ], "excerpt": "An assignment algorithm solves the linear assignment problem: given an n by n cost matrix of agents and tasks, it finds the minimum-cost one-to-one pairing, classically via Kuhn's 1955 Hungarian method.", "snippet": "An assignment algorithm solves the linear assignment problem: given an n by n cost matrix of agents and tasks, it finds the minimum-cost one-to-one pairing, classically via Kuhn's 1955 Hungarian method.", "node": "physical.math.discrete.discrete.combinatorics", "markdown": "# Assignment algorithm\n\nAn assignment algorithm solves the linear assignment problem: given a set of agents and a set of tasks with a cost or score for every agent–task pair, it finds the one-to-one pairing that minimizes total cost or maximizes total benefit. The input is an \\( n \\times n \\) cost matrix \\( C = (c_{ij}) \\), and the output is a permutation matching each row to a distinct column with minimum sum of selected entries.[1](https://epubs.siam.org/doi/book/10.1137/1.9781611972238) The Hungarian algorithm runs in polynomial time and was first proposed by Kuhn in 1955.[2](https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss11/OPT/lec11.pdf)\n\n| Key fact | Detail |\n|---|---|\n| Problem | Select exactly one entry per row and column of an \\( n \\times n \\) cost matrix, minimizing the sum[1](https://epubs.siam.org/doi/book/10.1137/1.9781611972238) |\n| Classic method | Hungarian method, published by H. W. Kuhn in Naval Research Logistics Quarterly, 1955[3](https://doi.org/10.1002/nav.3800020109) |\n| Complexity | \\( O(n^4) \\) in Kuhn's original form; \\( O(n^3) \\) in later implementations[4](https://luc.devroye.org/Gameroff+Campana-The_Hungarian_Method-COMP252-2024.pdf) |\n| Main alternatives | Shortest augmenting path (Jonker–Volgenant), auction algorithm, cost-scaling[5](https://doi.org/10.1007/bf02278710) • [6](https://doi.org/10.1007/bf01584237) • [7](https://doi.org/10.1007/bf01585996) |\n| Best known bound | \\( O(\\sqrt{n} \\cdot m \\cdot \\log(n \\cdot N)) \\) for integral costs (Gabow–Tarjan)[8](https://www.columbia.edu/~cs2035/courses/ieor8100.F18/GabTar.pdf) |\n| Typical uses | Multi-target tracking, input-queued switching, logistics, and data association[9](https://www.cs.princeton.edu/courses/archive/spr05/cos423/lectures/07assignment.pdf) • [1](https://epubs.siam.org/doi/book/10.1137/1.9781611972238) |\n\n## How it works\n\nThe assignment problem is equivalent to finding a minimum-cost perfect matching in a complete bipartite graph with one node per row, one per column, and edge costs \\( c_{ij} \\).[10](https://public.websites.umich.edu/~murty/books/network_programming/network-3.pdf) The Hungarian method is a primal-dual algorithm: it maintains dual variables \\( u_i \\) for rows and \\( v_j \\) for columns satisfying \\( u_i + v_j \\le c_{ij} \\), and maximizes \\( \\sum_i u_i + \\sum_j v_j \\).[2](https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss11/OPT/lec11.pdf) The reduced cost is \\( \\bar{c}_{ij} = c_{ij} - u_i - v_j \\); by duality, an assignment is optimal when every assigned edge has \\( \\bar{c}_{ij} = 0 \\), the complementary slackness condition.[2](https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss11/OPT/lec11.pdf) Kuhn framed the dual as finding non-negative integers \\( u_1, \\ldots, u_n \\) and \\( v_1, \\ldots, v_n \\) with \\( u_i + v_j \\ge r_{ij} \\) that minimize \\( \\sum u_i + \\sum v_j \\), a set he called a cover.[11](https://www.math.toronto.edu/mccann/1855/KuhnNRL55.pdf)\n\nThe key intuition is that adding or subtracting a constant along a row or column does not change which perfect matching is cheapest.[9](https://www.cs.princeton.edu/courses/archive/spr05/cos423/lectures/07assignment.pdf) The method therefore transforms the matrix toward zero entries while tracking the transformation in the duals. A result of König underpins the matching step: if the largest number of independent marks that can be chosen is \\( m \\), then \\( m \\) lines contain all marked positions.[11](https://www.math.toronto.edu/mccann/1855/KuhnNRL55.pdf) König's 1916 matching/vertex-cover duality was extended to the weighted case; the proof gave no explicit algorithm but implicitly defines the iterative procedure Kuhn developed.[12](http://www.inf.u-szeged.hu/~csendes/EgervarySI/MartelloFinal.pdf)\n\n## How it is done\n\nA standard \\( O(n^3) \\) implementation proceeds as follows[2](https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss11/OPT/lec11.pdf):\n\n1. Subtract each row's minimum from that row, then each column's minimum from that column, producing a non-negative matrix with a zero in every row and column and duals \\( u_i, v_j \\) equal to the subtracted amounts.\n2. Find a maximum matching using only zero-reduced-cost edges, growing an alternating tree from an unmatched row.\n3. If the matching is perfect, stop: it is optimal by complementary slackness.\n4. Otherwise compute \\( \\alpha = \\min \\{ \\bar{c}_{ij} \\} \\) over entries not covered by the tree, and update the duals, \\( u_i \\leftarrow u_i + \\alpha \\) for rows in the tree and \\( v_j \\leftarrow v_j - \\alpha \\) for columns in it.[2](https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss11/OPT/lec11.pdf)\n5. Repeat from step 2; each of the \\( n \\) matching augmentations takes \\( O(n^2) \\), giving \\( O(n^3) \\) overall.[4](https://luc.devroye.org/Gameroff+Campana-The_Hungarian_Method-COMP252-2024.pdf)\n\nKuhn's 1955 version takes at most \\( O(n^4) \\).[10](https://public.websites.umich.edu/~murty/books/network_programming/network-3.pdf) Credit for the \\( O(n^3) \\) improvement is reported differently across the literature: one line attributes it to Tomizawa (1971) and independently Edmonds and Karp (1972)[4](https://luc.devroye.org/Gameroff+Campana-The_Hungarian_Method-COMP252-2024.pdf), while textbook accounts credit Lawler's 1976 implementation via successive shortest path techniques[10](https://public.websites.umich.edu/~murty/books/network_programming/network-3.pdf); the published literature does not resolve the attribution.\n\n## Origin\n\nKuhn published the Hungarian method in Naval Research Logistics Quarterly 2(1–2), pp. 83–97, in March 1955.[3](https://doi.org/10.1002/nav.3800020109) • [13](https://doi.org/10.1007/bf01456961) • [12](http://www.inf.u-szeged.hu/~csendes/EgervarySI/MartelloFinal.pdf) Kuhn translated Egerváry's paper from Hungarian into English in the fall of 1953, and the combination with König's result provided the algorithm's basis.[14](https://www.math.utoronto.ca/mccann/1855/KuhnEJOR12.pdf) Kuhn noted that these ideas predate the birth of linear programming by more than 15 years.[3](https://doi.org/10.1002/nav.3800020109)\n\nJames Munkres published a variant of Kuhn's algorithm with a correctness proof, generalized to the transportation problem, in the Journal of the Society for Industrial and Applied Mathematics 5(1), pp. 32–38, in March 1957.[15](https://doi.org/10.1137/0105003) • [16](https://www.sciencedirect.com/science/article/abs/pii/S0377221705007137) Jacobi's posthumous papers, published in 1890 after his death in 1851, contain an algorithm essentially identical to the Hungarian method.[14](https://www.math.utoronto.ca/mccann/1855/KuhnEJOR12.pdf)\n\n## Variants\n\n**Shortest augmenting path.** Tomizawa observed in 1971 that shifting to non-negative reduced costs lets [Dijkstra's algorithm](https://www.edgepedia.org/dijkstras-algorithm) solve the shortest-path subproblems; with \\( O(n) \\) augmentations this yields \\( O(n^3) \\).[17](https://doi.org/10.1002/net.3230010206) • [18](https://gwern.net/doc/statistics/decision/1987-jonker.pdf) The Jonker–Volgenant algorithm (LAPJV), published in [Computing](https://www.edgepedia.org/computing) in 1987, adds new initialization routines and a special Dijkstra implementation; both its initialization and augmentation phases run in \\( O(n^3) \\), and on sparse problems it was uniformly faster than the best algorithms then in the literature.[5](https://doi.org/10.1007/bf02278710)\n\n**Auction algorithm.** Dimitri P. Bertsekas introduced the auction algorithm in Mathematical Programming in 1981[6](https://doi.org/10.1007/bf01584237), motivated by parallelism; unassigned persons bid for objects, prices act as dual variables, and the bidding increment guarantees \\( \\varepsilon \\)-complementary slackness, so the final cost is within \\( n \\cdot \\varepsilon \\) of optimal.[19](https://web.mit.edu/dimitrib/www/Auction_Survey.pdf) The Jacobi version, in which all unassigned agents bid simultaneously, suits parallel computation, and the reverse auction handles asymmetric problems and reduces price wars.[20](https://web.mit.edu/dimitrib/www/Ch2_AUCTION.pdf) The algorithm was improved with \\( \\varepsilon \\)-scaling to \\( O(n^3 \\log(n \\cdot C)) \\), where \\( C = \\max |c_{ij}| \\).[21](https://cris.unibo.it/retrieve/e1dcb335-c29e-7715-e053-1705fe0a6cc9/1047369.pdf)\n\n**Cost scaling.** Goldberg and Kennedy's cost-scaling push-relabel algorithm appeared in Mathematical Programming in 1995[7](https://doi.org/10.1007/bf01585996); the best strongly polynomial bound, \\( O(n(m + n \\log n)) \\) with \\( n \\) nodes and \\( m \\) edges, is achieved by the Hungarian method, while Gabow and Tarjan's scaling algorithm runs in \\( O(\\sqrt{n} \\cdot m \\cdot \\log(n \\cdot N)) \\) for integral costs.[22](https://homes.di.unimi.it/righini/Didattica/OttimizzazioneSuGrafo/MaterialeOG/1995%20Goldberg%20Kennedy%20-%20Cost%20scaling%20for%20assignment%20problem.pdf) • [8](https://www.columbia.edu/~cs2035/courses/ieor8100.F18/GabTar.pdf) Parallel work began early: Wein and Zenios studied massively parallel solution in 1991[23](https://doi.org/10.1016/0743-7315%2891%2990092-n), and Date and Nagi built GPU-accelerated Hungarian algorithms in 2016.[24](https://doi.org/10.1016/j.parco.2016.05.012)\n\n## Applications\n\nAssignment solvers appear wherever detections must be matched to tracks or resources to demands. Multi-target tracking with sensors of limited resolution produces multiassignment problems of exactly this form[20](https://web.mit.edu/dimitrib/www/Ch2_AUCTION.pdf), and multi-index assignment problems have recent applications in multi-target tracking and data association.[1](https://epubs.siam.org/doi/book/10.1137/1.9781611972238) In input-queued packet switching, FIFO queueing limits throughput to 58% under uniform arrivals, while maximum-weight matching achieves 100%.[9](https://www.cs.princeton.edu/courses/archive/spr05/cos423/lectures/07assignment.pdf)\n\n## Limitations and alternatives\n\nBrute force is hopeless at scale: the number of permutations of \\( n \\) elements is \\( n! \\), so enumeration is infeasible for large instances.[25](https://www.mdpi.com/1999-4893/15/10/377) Auction algorithms can handle asymmetric (rectangular) instances with unequal numbers of persons and objects directly in suitable formulations, with termination guaranteed when at least one feasible assignment exists.[30](https://faculty.engineering.asu.edu/sites/g/files/litvpz5506/files/2026-06/A-Forward-Reverse-Auction-Algorithm-for-Asymmetric-Assignment-Problems.pdf) • [26](https://ar5iv.labs.arxiv.org/html/1810.03562) Adaptations of auction-style methods to assignment with subset capacity constraints have been shown to cycle on some instances, failing to terminate.[27](https://ulrich-bauer.org/pub/ConstrainedAssignment.pdf)\n\nRectangular (unbalanced) problems are commonly handled by padding the matrix to \\( n \\times n \\) with \\( n = \\max(r, c) \\) using zero-cost dummy entries, and maximization is converted to minimization by negating all costs and negating the final answer.[28](https://neelmishra.github.io/blog/cp/optimization/hungarian-detailed.html) Forbidden assignments are handled by omitting the corresponding arcs, effectively setting \\( c_{ij} = +\\infty \\).[10](https://public.websites.umich.edu/~murty/books/network_programming/network-3.pdf) A computational comparison of eight codes (APC, CTCS, LAPm, JV, NAUCTION_SP, AFLP, AFR, CSA) on dense instances found no precise ranking: the fastest code depends on the cost class.[21](https://cris.unibo.it/retrieve/e1dcb335-c29e-7715-e053-1705fe0a6cc9/1047369.pdf) Because the LP relaxation of the assignment problem is integral, with basic solutions corresponding to permutation matrices, the Hungarian method and its relatives solve the linear program exactly.[29](https://www.andrew.cmu.edu/course/42-731/handouts/Burkard%5FLAP%5Freview.pdf)\n\n## References\n\n1. [Assignment Problems (Burkard, Dell'Amico, Martello, SIAM)](https://epubs.siam.org/doi/book/10.1137/1.9781611972238)\n2. [Optimization I Lecture 11: The Assignment Problem and Primal-Dual Algorithms (MPI-INF)](https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss11/OPT/lec11.pdf)\n3. [H. W. Kuhn (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly.](https://doi.org/10.1002/nav.3800020109)\n4. [The Hungarian Method (Gameroff & Campana, COMP252 lecture transcript, McGill, 2024)](https://luc.devroye.org/Gameroff+Campana-The_Hungarian_Method-COMP252-2024.pdf)\n5. [R. Jonker, A. Volgenant (1987). A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing.](https://doi.org/10.1007/bf02278710)\n6. [Dimitri P. Bertsekas (1981). A new algorithm for the assignment problem. Mathematical Programming.](https://doi.org/10.1007/bf01584237)\n7. [Andrew V. Goldberg, Robert Kennedy (1995). An efficient cost scaling algorithm for the assignment problem. Mathematical Programming.](https://doi.org/10.1007/bf01585996)\n8. [Faster scaling algorithms for network problems (Gabow & Tarjan)](https://www.columbia.edu/~cs2035/courses/ieor8100.F18/GabTar.pdf)\n9. [Assignment Problem (Kleinberg–Tardos slides, Princeton COS 423, Kevin Wayne)](https://www.cs.princeton.edu/courses/archive/spr05/cos423/lectures/07assignment.pdf)\n10. [Network Programming, Chapter 3: The Hungarian Method (Ahuja, Magnanti, Orlin / Murty)](https://public.websites.umich.edu/~murty/books/network_programming/network-3.pdf)\n11. [The Hungarian method for the assignment problem (full text PDF)](https://www.math.toronto.edu/mccann/1855/KuhnNRL55.pdf)\n12. [Jenő Egerváry: from the origins of the Hungarian algorithm to satellite communication (Martello et al.)](http://www.inf.u-szeged.hu/~csendes/EgervarySI/MartelloFinal.pdf)\n13. [Dénes König (1916). Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Mathematische Annalen.](https://doi.org/10.1007/bf01456961)\n14. [A tale of three eras: The discovery and rediscovery of the Hungarian Method (Kuhn, 2012)](https://www.math.utoronto.ca/mccann/1855/KuhnEJOR12.pdf)\n15. [James Munkres (1957). Algorithms for the Assignment and Transportation Problems. Journal of the Society for Industrial and Applied Mathematics.](https://doi.org/10.1137/0105003)\n16. [Assignment problems: A golden anniversary survey (Pentico, EJOR)](https://www.sciencedirect.com/science/article/abs/pii/S0377221705007137)\n17. [N. Tomizawa (1971). On some techniques useful for solution of transportation network problems. Networks.](https://doi.org/10.1002/net.3230010206)\n18. [A shortest augmenting path algorithm for dense and sparse linear assignment problems (Jonker & Volgenant, Computing 38, 1987)](https://gwern.net/doc/statistics/decision/1987-jonker.pdf)\n19. [Auction algorithms for network flow problems: A tutorial introduction (Bertsekas)](https://web.mit.edu/dimitrib/www/Auction_Survey.pdf)\n20. [Auction Algorithms for the Assignment Problem (book chapter, Bertsekas)](https://web.mit.edu/dimitrib/www/Ch2_AUCTION.pdf)\n21. [Review Article (assignment problem algorithms survey, University of Bologna repository)](https://cris.unibo.it/retrieve/e1dcb335-c29e-7715-e053-1705fe0a6cc9/1047369.pdf)\n22. [Cost scaling for the assignment problem (Goldberg & Kennedy, 1995)](https://homes.di.unimi.it/righini/Didattica/OttimizzazioneSuGrafo/MaterialeOG/1995%20Goldberg%20Kennedy%20-%20Cost%20scaling%20for%20assignment%20problem.pdf)\n23. [On the massively parallel solution of the assignment problem (Journal of Parallel and Distributed Computing, 1991)](https://doi.org/10.1016/0743-7315%2891%2990092-n)\n24. [Ketan Date, Rakesh Nagi (2016). GPU-accelerated Hungarian algorithms for the Linear Assignment Problem. Parallel Computing.](https://doi.org/10.1016/j.parco.2016.05.012)\n25. [The Assignment Problem and Its Relation to Logistics Problems (Algorithms, MDPI)](https://www.mdpi.com/1999-4893/15/10/377)\n26. [The equivalence between two classic algorithms for the assignment problem](https://ar5iv.labs.arxiv.org/html/1810.03562)\n27. [Assignment Problem with Constraints (Bauer, thesis)](https://ulrich-bauer.org/pub/ConstrainedAssignment.pdf)\n28. [Hungarian Algorithm Walkthrough (Neel Mishra, 2025)](https://neelmishra.github.io/blog/cp/optimization/hungarian-detailed.html)\n29. [Linear Assignment Problems and Extensions (Burkard et al., review)](https://www.andrew.cmu.edu/course/42-731/handouts/Burkard%5FLAP%5Freview.pdf)\n30. [A Forward Reverse Auction Algorithm for Asymmetric Assignment Problems (faculty.engineering.asu.edu)](https://faculty.engineering.asu.edu/sites/g/files/litvpz5506/files/2026-06/A-Forward-Reverse-Auction-Algorithm-for-Asymmetric-Assignment-Problems.pdf)\n\n---\n*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Combinatorics*\n\n*Initially written Sep 29, 2026 · Reviewed: Sep 30, 2026 · Edited: Sep 30, 2026 · Last review: Sep 30, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [ "https://www.columbia.edu/~cs2035/courses/ieor8100.F18/GabTar.pdf", "https://public.websites.umich.edu/~murty/books/network_programming/network-3.pdf" ], "url": "https://www.edgepedia.org/assignment-algorithm", "markdown_url": "https://www.edgepedia.org/assignment-algorithm.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Assignment algorithm\", Edgepedia (EdgeChat), https://www.edgepedia.org/assignment-algorithm. Edgepedia Community License 1.0.", "credit_md": "\"[Assignment algorithm](https://www.edgepedia.org/assignment-algorithm)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/assignment-algorithm](https://www.edgepedia.org/assignment-algorithm). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Assignment algorithm\", Edgepedia (EdgeChat), https://www.edgepedia.org/assignment-algorithm. Edgepedia Community License 1.0.", "speakable": "An assignment algorithm solves the linear assignment problem: given an n by n cost matrix of agents and tasks, it finds the minimum-cost one-to-one pairing, classically via Kuhn's 1955 Hungarian method." }