logo

Algorithm - Bipart

Last Updated: 2021-12-15

Suppose we have a table of numbers like this (we can assume it is a square table):

20  2   1   3   4
5   1   14  8   9
15  12  17  17  11
16  1   1   15  18
20  13  15  5   11

Your job is to calculate the maximum sum of n numbers where n is the number of rows or columns in the table. The catch is each number must come from a unique row and column.

For example, selecting the numbers at (0,0), (1,1), (2,2), (3,3), and (4,4) is acceptable, but (0,0), (0,1), (2,2), (3,3), and (4,4) is not because the first two numbers were pulled from the same row.

This is the maximum cost bipartite matching problem. The classical way to solve it is by using the Hungarian algorithm.

Basically you have a bipartite graph: the left set is the rows and the right set is the columns. Each edge from row i to column j has cost matrix[i, j]. Find the matching that maximizes the costs.