https://jack.valmadre.net/notes/2020/12/08/non-perfect-linear-assignment/

/(G = (U,V,E)/)

• /(|U| = r/)
• /(|V| = n/)
• without loss of generality, assume /(r /leq n/)

/[/begin{bmatrix}
/infty & 3 & -1 //
/infty & 5 & /infty //
2 & -3 & 0 //
/end{bmatrix}/]

• /(E(i,j) = /infty/) means no connection
  • Missing edges
• /(E(i,j) = 0/) means cost is zero.
  • however, given that cost can be either positive or negative, zero can be chosen.

In a matching problem, there will be /(/nu/) chosen edges.

/[0</nu<=r
/]

Balanced

Balanced means /(r = n/)

two subsets have equal cardinality

Perfect/Complete Matching

note that the problem is not actuallysolved using a general-purpose ILP(integer linear programming) solver, it is just a convenient framework in which to express the problem

Perfect/Complete matching = every vertex has a match

The constraint that the sum of each row and column is equal to one ensures that each element has exactly one match.

Unbalanced

assume /(r < n/)

an unbalanced probem cannot have a perfect matching, since there will be at least /(n-r/) unmatched elements in the larger set.

One-sided Perfect Matching

One-sided Perfect Matching = every vertex in the smaller set has a match.

In one-sided perfect matching, /(/nu = r < n/)

What if there is no perfect matching?

Imperfect Matching(with given edge number)

- when there does not exist a (one-sided)perfect matching.

when /(/nu < r/), i.e. one-sided perfect matching cannot be achieved due to the lack of edges, all possible matchings are imperfect/incomplete.

[Note