Give them Jobs

Unfortunately LaTeX doesn't let me draw bipartite graphs so I'll try explaining this the best I can.

Let the matching of a person to a job be denoted as $(Person, Job)$ .

Going down the list and selecting the first available job, we find an initial matching:

$(1, 1), (2, 10), (3, 3), (4, 2), (5, 5), (6, 4), (7, 7), (8, 8), (9, 9), (10, 11), (11, 13), (12, 14), (13, 12), (14, 6), (15, 15), (16, 17), (17, None), (18, 16), (19, 18), (20, None)$ .

Using the maximum matching algorithm we construct a path from an unassigned person to an unassigned job.

$20 - 1 = 1 - 3 = 3 - 20$ $\rightarrow$ $20 = 1 - 1 = 3 - 3 = 20$

Where $(=)$ means is assigned to and $(-)$ means could be assigned to.

We now have an improved matching:

$(1, 3), (2, 10), (3, 20), (4, 2), (5, 5), (6, 4), (7, 7), (8, 8), (9, 9), (10, 11), (11, 13), (12, 14), (13, 12), (14, 6), (15, 15), (16, 17), (17, None), (18, 16), (19, 18), (20, 1)$ .

We use the maximum matching algorithm once more and get:

$17 - 2 = 4 - 1 = 20 - 7 = 7 - 17 = 16 - 19$ $\rightarrow$ $17 = 2 - 4 = 1 - 20 = 7 - 7 = 17 - 16 = 19$ .

This gives us a final and complete matching of:

$(1, 3), (2, 10), (3, 20), (4, 1), (5, 5), (6, 4), (7, 17), (8, 8), (9, 9), (10, 11), (11, 13), (12, 14), (13, 12), (14, 6), (15, 15), (16, 19), (17, 2), (18, 16), (19, 18), (20, 7)$ .

Since everyone is assigned, the answer is $\boxed{20}$

A complete matching is possible, making the answer $\boxed{20}$ :

$\begin{array}{|cc|cc|cc|cc|}\hline Cand. & Post & Cand. & Post & Cand. & Post & Cand. & Post \\\hline 1 & 1 & 6 & 12 & 11 & 11 & 16 & 19 \\ 2 & 20 & 7 & 13 & 12 & 14 & 17 & 8 \\ 3 & 9 & 8 & 2 & 13 & 5 & 18 & 3 \\ 4 & 6 & 9 & 17 & 14 & 4 & 19 & 18 \\ 5 & 7 & 10 & 16 & 15 & 15 & 20 & 10 \\ \hline \end{array}$

The answer for this particular data is $\boxed{20}$ . I came up with a solution based on integer programming. Let $X_{i,j}$ be a binary variable that assumes the value $1$ if candidate $i$ is assigned for job $j$ and $0$ otherwise. Then, our objective function is as follows:

$Maximize: \sum_{i=1}^{20}\sum_{j=1}^{20} X_{i,j}$

Subject to the following contraints:

• Each candidate gets only one job:

$\sum_{j=1}^{20} X_{i,j} = 1 , i = 1, 2, ... , 20$

• Each job is assigned to a single candidate:

$\sum_{i=1}^{20} X_{i,j} = 1 , j = 1, 2, ... , 20$

• Candidates'compatibility. Here we need to use the data provided for every single candidate. For example, considering candidate $18$ , we exclude jobs $2, 8, 14, 15, 17$ and $19$ :

$X_{18,2}=0,$ $X_{18,8}=0,$ $X_{18,14}=0,$ $X_{18,15}=0,$ and $X_{18,17}=0$

And so on, for the other candidates.

No complex algorithms used. I took the position with the fewest candidates qualified and assigned that position to the candidate that had the smallest skill set...from there i worked my way up till reaching skills found amongst more candidates but always tried to match that position to the candidate that had the fewest skills.

If you look at the eligible candidates, you realize that all positions can be filled by all the 20 candidates in a way that no one is left out. You need not do the arduous task of making a table and eliminating options.