Assignment problem: Difference between revisions

Revision as of 12:31, 12 March 2025

Latest revision as of 14:39, 21 July 2025

(5 intermediate revisions by 4 users not shown)

Line 1:

{{Short description|Combinatorial optimization problem}}

{{merge from|Linear bottleneck assignment problem|discuss=Talk:Linear bottleneck assignment problem#Merge proposal|date=March 2025}}

[[File:hungarian_algorithm_unbalanced_assignment_problem_example.svg|thumb|upright=2|Worked example of assigning tasks to an unequal number of workers using the [[Hungarian method]]]]

The '''assignment problem''' is a fundamental [[combinatorial optimization]] problem. In its most general form, the problem is as follows:

Line 49 ⟶ 46:

In the balanced assignment problem, both parts of the bipartite graph have the same number of vertices, denoted by ''n''.

One of the first polynomial-time algorithms for balanced assignment was the [[Hungarian algorithm]]. It is a ''global'' algorithm&nbsp;– it is based on improving a matching along augmenting paths (alternating paths between unmatched vertices). Its run-time complexity, when using [[Fibonacci heap]]s, is <math>O(mn + n^2\log n)</math>,<ref>{{Cite journal|last1=Fredman|first1=Michael L.|last2=Tarjan|first2=Robert Endre|date=1987-07-01|title=Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms|journal=J. ACM|volume=34|issue=3|pages=596–615|doi=10.1145/28869.28874|s2cid=7904683|issn=0004-5411|doi-access=free}}</ref> where ''m'' is a number of edges. This is currently the fastest run-time of a [[strongly polynomial]] algorithm for this problem. Some variants of the Hungarian algorithm also benefit from parallel computing, including GPU acceleration.<ref>{{Cite journal |last=Kawtikwar |first=Samiran |last2=Nagi |first2=Rakesh |date=2024-05-01 |title=HyLAC: Hybrid linear assignment solver in CUDA |url=https://linkinghub.elsevier.com/retrieve/pii/S0743731524000029 |journal=Journal of Parallel and Distributed Computing |volume=187 |pages=104838 |doi=10.1016/j.jpdc.2024.104838 |issn=0743-7315|doi-access=free }}</ref> If all weights are integers, then the run-time can be improved to <math>O(mn + n^2\log \log n)</math>, but the resulting algorithm is only weakly-polynomial.<ref>{{Cite journal|last=Thorup|first=Mikkel|date=2004-11-01|title=Integer priority queues with decrease key in constant time and the single source shortest paths problem|journal=Journal of Computer and System Sciences|series=Special Issue on STOC 2003|volume=69|issue=3|pages=330–353|doi=10.1016/j.jcss.2004.04.003|issn=0022-0000|doi-access=free}}</ref> If the weights are integers, and all weights are at most ''C'' (where ''C''>1 is some integer), then the problem can be solved in <math>O(m\sqrt{n} \log(n\cdot C))</math> weakly-polynomial time in a method called ''weight scaling''.<ref>{{Cite journal|last1=Gabow|first1=H.|last2=Tarjan|first2=R.|date=1989-10-01|title=Faster Scaling Algorithms for Network Problems|journal=SIAM Journal on Computing|volume=18|issue=5|pages=1013–1036|doi=10.1137/0218069|issn=0097-5397}}</ref><ref>{{Cite journal|last1=Goldberg|first1=A.|last2=Kennedy|first2=R.|date=1997-11-01|title=Global Price Updates Help|journal=SIAM Journal on Discrete Mathematics|volume=10|issue=4|pages=551–572|doi=10.1137/S0895480194281185|issn=0895-4801}}</ref><ref>{{Cite journal|last1=Orlin|first1=James B.|last2=Ahuja|first2=Ravindra K.|date=1992-02-01|title=New scaling algorithms for the assignment and minimum mean cycle problems|journal=Mathematical Programming|language=en|volume=54|issue=1–3|pages=41–56|doi=10.1007/BF01586040|s2cid=18213947|issn=0025-5610}}</ref>

In addition to the global methods, there are ''local methods'' which are based on finding local updates (rather than full augmenting paths). These methods have worse asymptotic runtime guarantees, but they often work better in practice. These algorithms are called [[auction algorithm]]s, push-relabel algorithms, or preflow-push algorithms. Some of these algorithms were shown to be equivalent.<ref>{{Cite journal |last1=Alfaro |first1=Carlos A. |last2=Perez |first2=Sergio L. |last3=Valencia |first3=Carlos E. |last4=Vargas |first4=Marcos C. |date=2022-06-01 |title=The assignment problem revisited |url=https://doi.org/10.1007/s11590-021-01791-4 |journal=Optimization Letters |language=en |volume=16 |issue=5 |pages=1531–1548 |doi=10.1007/s11590-021-01791-4 |s2cid=238644205 |issn=1862-4480|url-access=subscription }}</ref>

Some of the local methods assume that the graph admits a ''perfect matching''; if this is not the case, then some of these methods might run forever.<ref name=":0" />{{Rp|3}} A simple technical way to solve this problem is to extend the input graph to a ''complete bipartite graph,'' by adding artificial edges with very large weights. These weights should exceed the weights of all existing matchings, to prevent appearance of artificial edges in the possible solution.

Line 89 ⟶ 86:

=== Other methods and approximation algorithms===

Other approaches for the assignment problem exist and are reviewed by Duan and Pettie<ref>{{Cite journal|last1=Duan|first1=Ran|last2=Pettie|first2=Seth|date=2014-01-01|title=Linear-Time Approximation for Maximum Weight Matching|url= https://webdl.eecsacm.umich.eduorg/~pettiedoi/papers/ApproxMWM-JACM10.pdf1145/2529989 |journal=Journal of the ACM|volume=61|pages=1–23|language=EN|doi=10.1145/2529989|s2cid=207208641|url-access=subscription}}</ref> (see Table II). Their work proposes an [[approximation algorithm]] for the assignment problem (and the more general [[maximum weight matching]] problem), which runs in linear time for any fixed error bound.

== Many-to-many assignment{{Anchor|mtm}} ==

Line 117 ⟶ 114:

*[[Rank-maximal matching]]

*[[Secretary problem]]

*[[Stable marriagematching problem]]

*[[Stable roommates problem]]

*[[Weapon target assignment problem]]