Greedy approach suggestions for assigning objects

Question

Suppose there are three categories of people. Type X, Type Y, Type Z. In each type, there are two objects of subtype Type 'a' and type 'b'.

For example.

X: a1 , a2 , b1 , b2

Y: a3 , a4 , b3 , b4

Z: a5 , a6 , b5 , b6

Each object of type 'a' should be assigned with an object of type 'b'. But it is desirable not necessary to assign a type 'a' with type 'b' from different classes (X, Y, Z).

In this example, the optimal solution would be: a1 with b5 , a2 with b6 , a3 with b1 , a4 with b2 , a5 with b3 , a6 with b4 .

Non -optimal solution would be :

a1 with b5 , a2 with b6 , a5 with b1 , a6 with b2 , a3 with b3 , a4 with b4 .

(Non -optimal because a3 and a4 are assigned with b's of same type Y)

If we generalize, there can be n- number of Types (X,Y,Z, .....and so on) with different number of a's and b's in each (but total number of a's = total number of b's).

How to find an optimal solution?

Answer 1

This problem reduces to finding a maximum matching in a bipartite graph, which can be done easily by e.g. the Ford-Fulkerson algorithm. You construct the graph as follows:

Take all elements of type $a$ on one side and all elements of type $b$ on the other. Then, for any two elements $a_i,b_j$, draw an edge between them if they do not belong to the same category.

If there is a matching in the set with only, say, $k$ pairs belonging to the same category, then we can find a matching in our graph on $m-k$ edges, where $m$ is the number of a's (or b's).