Editing Assignment problem (section)

==Algorithms==
A naive solution for the assignment problem is to check all the assignments and calculate the cost of each one. This may be very inefficient since, with ''n'' agents and ''n'' tasks, there are ''n''! ([[factorial]] of ''n'') different assignments. 

Another naive solution is to greedily assign the pair with the smallest cost first, and remove the vertices; then, among the remaining vertices, assign the pair with the smallest cost; and so on. This algorithm may yield a non-optimal solution. For example, suppose there are two tasks and two agents with costs as follows:

* Alice: Task 1 = 1, Task 2 = 2.
* George: Task 1 = 5, Task 2 = 8.

The greedy algorithm would assign Task 1 to Alice and Task 2 to George, for a total cost of 9; but the reverse assignment has a total cost of 7.

Fortunately, there are many algorithms for finding the optimal assignment in time [[polynomial time|polynomial]] in ''n''. The assignment problem is a special case of the [[transportation problem]], which is a special case of the [[minimum cost flow problem]], which in turn is a special case of a [[linear program]].  While it is possible to solve any of these problems using the [[simplex algorithm]], or in worst-case polynomial time using the [[ellipsoid method]], each specialization has a smaller solution space and thus more efficient algorithms designed to take advantage of its special structure.

=== Balanced assignment ===
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}}</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.

As shown by Mulmuley, Vazirani and Vazirani,<ref>{{Cite journal|last1=Mulmuley|first1=Ketan|last2=Vazirani|first2=Umesh|author-link2=Umesh Vazirani|last3=Vazirani|first3=Vijay|author-link3=Vijay Vazirani|year=1987|title=Matching is as easy as matrix inversion|journal=Combinatorica|volume=7|issue=1|pages=105–113|doi=10.1007/BF02579206|s2cid=47370049|author-link1=Ketan Mulmuley}}</ref> the problem of minimum weight perfect matching is converted to finding minors in the [[adjacency matrix]] of a graph. Using the [[isolation lemma]], a minimum weight perfect matching in a graph can be found with probability at least {{frac|1|2}}. For a graph with ''n'' vertices, it requires <math> O(\log^2(n)) </math> time.

=== Unbalanced assignment ===
In the unbalanced assignment problem, the larger part of the bipartite graph has ''n'' vertices and the smaller part has ''r''<''n'' vertices. There is also a constant ''s'' which is at most the cardinality of a maximum matching in the graph. The goal is to find a minimum-cost matching of size exactly ''s''. The most common case is the case in which the graph admits a one-sided-perfect matching (i.e., a matching of size ''r''), and ''s''=''r''.

Unbalanced assignment can be reduced to a balanced assignment. The naive reduction is to add <math>n-r</math> new vertices to the smaller part and connect them to the larger part using edges of cost 0. However, this requires <math>n(n-r)</math> new edges. A more efficient reduction is called the ''doubling technique''. Here, a new graph ''G'<nowiki/>'' is built from two copies of the original graph ''G'': a forward copy ''Gf'' and a backward copy ''Gb.'' The backward copy is "flipped", so that, in each side of ''G''', there are now ''n''+''r'' vertices. Between the copies, we need to add two kinds of linking edges:<ref name=":0" />{{Rp|4–6}}

* Large-to-large: from each vertex in the larger part of ''Gf'', add a zero-cost edge to the corresponding vertex in ''Gb''.
* Small-to-small: if the original graph does not have a one-sided-perfect matching, then from each vertex in the smaller part of ''Gf'', add a very-high-cost edge to the corresponding vertex in ''Gb''.

All in all, at most <math>n+r</math> new edges are required. The resulting graph always has a perfect matching of size <math>n+r</math>. A minimum-cost perfect matching in this graph must consist of minimum-cost maximum-cardinality matchings in ''Gf'' and ''Gb.''  The main problem with this doubling technique is that there is no speed gain when <math>r\ll n</math>.

Instead of using reduction, the unbalanced assignment problem can be solved by directly generalizing existing algorithms for balanced assignment. The [[Hungarian algorithm]] can be generalized to solve the problem in <math>O(ms + s^2\log r)</math> strongly-polynomial time. In particular, if ''s''=''r'' then the runtime is <math>O(mr + r^2\log r)</math>.   If the weights are integers, then Thorup's method can be used to get a runtime of <math>O(ms + s^2\log \log r)</math>.<ref name=":0" />{{Rp|6}}

=== Solution by linear programming ===
The assignment problem can be solved by presenting it as a [[linear program]]. For convenience we will present the maximization problem. Each edge {{math|(''i'',''j'')}}, where ''i'' is in A and ''j'' is in T, has a weight <math display="inline">w_{ij}</math>. For each edge {{tmath|(i,j)}} we have a variable <math display="inline">x_{ij}</math><sub>.</sub> The variable is 1 if the edge is contained in the matching and 0 otherwise, so we set the domain constraints:  
<math display="block">0\le x_{ij}\le 1\text{ for }i,j\in A,T, \, </math> <math display="block">x_{ij}\in \mathbb{Z}\text{ for }i,j\in A,T. </math>

The total weight of the matching is: <math>\sum_{(i,j)\in A\times T} w_{ij}x_{ij}</math>. The goal is to find a maximum-weight perfect matching.

To guarantee that the variables indeed represent a perfect matching, we add constraints saying that each vertex is adjacent to exactly one edge in the matching, i.e.,  
<math display="block">\sum_{j\in T}x_{ij}=1\text{ for }i\in A, \,
~~~
\sum_{i\in A}x_{ij}=1\text{ for }j\in T, \, </math>.

All in all we have the following LP:

<math display="block">\text{maximize}~~\sum_{(i,j)\in A\times T} w_{ij}x_{ij}
</math><math display="block">\text{subject to}~~\sum_{j\in T}x_{ij}=1\text{ for }i\in A, \,
~~~
\sum_{i\in A}x_{ij}=1\text{ for }j\in T </math><math display="block">0\le x_{ij}\le 1\text{ for }i,j\in A,T, \, </math><math display="block">x_{ij}\in \mathbb{Z}\text{ for }i,j\in A,T. </math>This is an integer linear program.  However, we can solve it without the integrality constraints (i.e., drop the last constraint), using standard methods for solving continuous linear programs. While this formulation allows also fractional variable values, in this special case, the LP always has an optimal solution where the variables take integer values.  This is because the constraint matrix of the fractional LP is [[Unimodular matrix#Total unimodularity|totally unimodular]]&nbsp;– it satisfies the four conditions of Hoffman and Gale.

=== 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://dl.acm.org/doi/10.1145/2529989 |journal=Journal of the ACM|volume=61|pages=1–23|language=EN|doi=10.1145/2529989|s2cid=207208641}}</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.