P90: Enumeration of all assignment

P90: Enumeration of all assignment

Input:

An integer $n$ and $n \times n$ cost matrix $C = (c_{ij})$.

Output:

All assignments that minimizes $\sum^{i=n}_{i=1}\sum^{j=n}_{j=1} c_{ij}x_{ij}$ subject to $\sum^{i=n}_{i=1} x_{ij} = 1 \; (j = 1, \dots, n)$, $\sum^{j=n}_{j=1} x_{ij} = 1\; (i = 1, \dots, n)$, and $x_{ij} \ge 0$.

Complexity:

Comment:

Reference:

[Murty1968] (Bibtex)