Editing Assignment problem (section)

=== 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}}