Matching and allocation

After studying this section you should be able to:

use bipartite graphs to model matchings
understand the conditions for matchings to be maximal or complete
apply the maximum matching algorithm

Matchings and graphs

A bipartite graph is a graph in which the vertices are divided into two sets such that no pair of vertices in the same set is connected by an edge. In this case, the two sets are {A, B, C} and {p, q, r, s}.

Some vertices in a bipartite graph may not be connected to another vertex.

A matching between two sets may be represented by a bipartite graph in which there is at most one edge connecting a pair of vertices.

A maximal matching is a matching which has the maximum number of edges. This occurs when every vertex in one of the sets is connected to a vertex in the other set. The bipartite graph shown above represents a maximal matching.

A complete matching is a matching in which every vertex is connected to another vertex. This can only occur when the two sets contain the same number of vertices.

The matching improvement algorithm

Figure 1 is a bipartite graph showing the possible connections between two sets. It does not represent a matching because some vertices have more than one connection.

Figure 2 is a bipartite graph representing an initial matching.

An initial matching may be improved by increasing the number of connections. This is the purpose of the matching improvement algorithm.

Step 1 In the initial matching, start from a vertex that is not connected and look for an alternating path to a vertex in the other set that is not connected.
Step 2 Each edge on the alternating path, not included in the initial matching, is now included and each edge originally included is removed.
Step 3 Repeat steps 1 and 2 using the latest matching in place of the initial matching until no further alternating paths can be found.

In an alternating path, the edges alternate between those from the bipartite graph that are not in the initial matching and those that are.

Allocation problems

In an allocation (or assignment) problem, the object is to set up a matching that will optimise a particular objective, such as minimising a cost or maximising a profit. If we regard one set of objects as agents and the other set as tasks, then the

underlying assumptions are that:

Any agent may be assigned to any task (unlike the matching problems).
Each agent is assigned at most one task and each task has at most one agent assigned to it.

When the number of agents is equal to the number of tasks, the problem is said to be balanced. If the number of agents exceeds the number of tasks, or vice versa, then the problem is unbalanced. The technique for solving an unbalanced problem involves introducing a dummy agent or task which then allows the solution to proceed as for the balanced case. In the solution of an unbalanced problem, a task assigned to a dummy agent isn’t actually completed and an agent assigned to a dummy task doesn’t actually have a task to carry out.

The opportunity cost matrix

The Hungarian algorithm

The Hungarian algorithm is used to find the allocation that optimises the given objective.

Step 1 Find the opportunity cost matrix.
Step 2 Test for optimality. If true then make the allocation and stop.
Step 3 Revise the opportunity cost matrix and repeat step 2.

Maximising allocation problems

If the objective involves maximising a quantity, such as a profit, then the first step is to subtract every value in the original matrix from a fixed value. This fixed value may be taken to be the largest value in the matrix or any value larger than this. The Hungarian algorithm is now applied in the usual way to this transformed matrix.

PROGRESS CHECK

Log in