`matchpairs`

Optimal assignment of rows to columns of a cost matrix.

Syntax

M = matchpairs(Cost, costUnmatched)

Returns the row/column pairs of the minimum-cost matching.

[M, uR, uC] = matchpairs(Cost, costUnmatched)

Also returns the indices of the rows and columns left unmatched.

Description

This is the linear assignment problem with an option to skip. A pair is accepted only if its cost is lower than leaving both partners unmatched, so a small costUnmatched produces fewer pairs. The total cost minimized is the sum of the chosen entries plus costUnmatched for every unmatched row or column.

Typical uses are tracking objects between frames, matching two lists of points, and pairing workers with tasks.

Input arguments

Cost: Matrix where Cost(i, j) is the cost of pairing row i with column j.
costUnmatched: Positive scalar: the penalty paid for leaving a row or a column without a partner.

Output arguments

M: Two-column matrix; each row [i j] pairs row i with column j.
uR, uC: Column vectors with the unmatched rows and unmatched columns.

Example

A row left unmatched

C = [1 5; 6 2; 9 9];
[M, uR, uC] = matchpairs(C, 4)

Output

M = 2×2

     1     1
     2     2
uR = 3
uC = 0×1 empty double column vector

matchpairs