Assignment problem: Difference between revisions

Revision as of 00:26, 26 March 2021

Revision as of 18:22, 17 May 2021

Line 46:

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