Matching

Matching problems involve optimising the allocation of tasks to achieve the most efficient outcome. By evaluating factors such as time, cost, or resources, the optimal way to organise and assign tasks can be determined. For example, in a project setting, tasks can be assigned to team members based on their expertise, availability, and the time required to complete each task. This ensures that the project is completed efficiently while minimising delays and costs.

Use this page to revise the following concepts within matching:

• Different Representations
• Hungarian Algorithm

Different Representations

A bipartite graph is a type of graph in which the vertices are divided into two distinct sets which are typically arranged in two columns. Edges connect vertices from one set to the other, but not within the same set. Depending on the context of the problem, these edges can be either directed or undirected, representing different types of relationships or assignments.

For example, consider a scenario where persons \(A, B\) and \(C\) are assigned to complete tasks \(X, Y\) and \(Z\). This could be represented as a bipartite graph:

This bipartite graph describes the following relationships:

• Person \(A\) can complete tasks \(X\) or \(Y\)
• Person \(B\) can complete tasks \(X\) or \(Z\)
• Person \(C\) can complete task \(Y\)

To ensure that all tasks are completed by one person, the graph can be simplified by assigning specific tasks. \(C\) must complete task \(Y\). Since \(A\) must complete either \(Y\) or \(X\), this leaves \(A\) to complete task \(X\). Since \(B\) must complete \(X\) or \(Z\), this leaves \(B\) to complete task \(Z\).

This example demonstrates how a bipartite graph can use constraints to optimise task allocation. While this example is simple and does not include weighted edges, weighted edges could represent additional factors such as the time required to complete each task. In scenarios where multiple options exist for assigning tasks, these weights would play a crucial role in determining the allocation.

However, as the number of vertices increases, the number of options that exist for assigning tasks increases, or the weights become more similar, manually finding the optimal solution becomes significantly more complex. In such cases, the Hungarian algorithm can be used to efficiently determine the optimal allocation in weighted bipartite graphs.

Hungarian Algorithm

The Hungarian Algorithm optimises task allocation by finding the solution with the minimum total weight by using a cost matrix. This explanation focuses on its application to complete graphs with equal numbers of vertices in each set.

The algorithm is applicable only to weighted bipartite graphs with non-negative values and ensures that each vertex in one set is assigned to exactly one vertex in the other set.

The steps involved in the Hungarian Algorithm are:

1. Construct the square \((n\times n)\) cost matrix (if not provided) where:
   1. The rows represent those completing tasks
   2. The columns represent the tasks assigned
2. Row reduction: subtract the lowest value from each row.
3. Minimum number of lines check: cover all the zeros in the matrix using the minimum number of horizontal or vertical lines. If the number of lines equals to the number of row or columns \((n)\) then the optimal solution is found. If not, proceed to next step.
4. Column reduction: subtract the lowest value from each column. If there is already a zero in the column, the column remains unchanged as zero is the lowest value.
5. Minimum number of lines check
6. Uncovered values: find the lowest value from all the uncovered values, and:
   1. Subtract it from any other uncovered values
   2. Add it to any intersecting covering lines
7. Repeat step 5-6 until the number of minimum lines equals to the number or rows or columns \((n)\)
8. Assign the allocations: zeros in the cost matrix represent the corresponding lowest allocation for those completing it and the task assigned. Make the allocation such that each row and column is only assigned once.
9. Find the minimum cost: sum the weights that correspond to the assigned tasks.

Back Next