Minimum-Cost Bipartite Graph Matching

Let there be $N$ agents and $N$ tasks, where any agent can be assigned (i.e. matched) to perform any task under some cost.

The problem is to perform all $N$ tasks by assigning exactly one agent to a task and one task to an agent so that the total cost of the matching is minimised.

Example Of Minimum-Cost Bipartite Graph Solution

• The result matrix would actually be a boolean matrix with 1 to signify where an edge exists.
• As its a perfect matching, any row or column in the boolean matrix must sum to $1$

Formalisation Of The Problem

Let $x_{i,j}$ be a binary variable such that:

$$x_{i,j}=\{\begin{array}{ll}1,& \text{if Agent }i\text{ is assigned to Task }j\\ 0,& \text{otherwise}\end{array}$$

Let $c_{i,j}$ be the cost of assigning agent $i$ to task $j$ where $i,j\le N$.

The problem is thus to minimise total assignment cost, i.e. minimise the objective function:

$$z=\sum _{i=1}^N\sum _{j=1}^N{c}_{i,j}{x}_{i,j}$$

Subjected to the following constraints:

1. Each task is assigned to exactly one agent:

$$\sum _{i=1}^N{x}_{i,j}=1\forall j\in [1,N]$$

2. Each agent is assigned to exactly one task:

$$\sum _{j=1}^N{x}_{i,j}=1\forall i\in [1,N]$$

3. Binary assignment constraint:

$$x_{i,j}\in \{0,1\}\forall i,j$$

Adding a constant to any row or column of the cost matrix does not affect the optimal assignment.

• For a row, the constant is added to all options for a given agent, and for a column, to all options for a given task.
• Since each agent is assigned to one task and each task to one agent, the constant contributes equally to all feasible assignments and thus does not change the optimal solution.

Transforming The Objective Function

some linking sentence…Transforming the objective function to motivate the method/algorithm that follows

$$z=\sum _{i=1}^N\sum _{j=1}^N{c}_{i,j}{x}_{i,j}$$

Introduce dual variables (similar to slack variables) $u_i$ for the row constraint, and $v_j$ for the column constraint, and substitute $c_{i,j}$ with $c_{i,j}=(c_{i,j}-u_i-v_j+u_i+v_j)$, which is algebraically valid.

$$z=\sum _{i=1}^N\sum _{j=1}^N{x}_{i,j}(c_{i,j}-u_i-v_j+u_i+v_j)$$

Distribute $x_{i,j}$ across the sum inside the parentheses.

$$z=\sum _{i=1}^N\sum _{j=1}^N{x}_{i,j}(c_{i,j}-u_i-v_j)+\sum _{i=1}^N\sum _{j=1}^N{x}_{i,j}{u}_i+\sum _{i=1}^N\sum _{j=1}^N{x}_{i,j}{v}_j$$

Take constants $u_i$ and $v_j$ outside the respective summations over $j$ and $i$.

$$z=\sum _{i=1}^N\sum _{j=1}^N{x}_{i,j}(c_{i,j}-u_i-v_j)+\sum _{i=1}^N{u}_i\sum _{j=1}^N{x}_{i,j}+\sum _{j=1}^N{v}_j\sum _{i=1}^N{x}_{i,j}$$

From the problem constraints:

$$\sum _{j=1}^N{x}_{i,j}=1\text{and}\sum _{i=1}^N{x}_{i,j}=1$$

Therefore:

$$z=\sum _{i=1}^N\sum _{j=1}^N{x}_{i,j}(c_{i,j}-u_i-v_j)+\sum _{i=1}^N{u}_i+\sum _{j=1}^N{v}_j$$

So $x_{i,j}$ can either be $0$ or $1$. If $x_{i,j}=0$, this means row (agent) $i$ has not been assigned to column (task) $j$, in this case the first term disappears and the objective function is equal to the second and third term only.

When $x_{i,j}=1$, we want a method to set $c_{i,j}^{\prime }=c_{i,j}-u_i-v_j$ to $0$. Thus for any assignment , we insist that $c_{i,j}=u_i+v_j$ so that $c_{i,j}^{\prime }=0$.

What this means is that the term disappears whether or not we have an asisgnment. So we wanna choose $u_i$ and $v_j$ values in some special way such that when there is an assignment $x_{i,j}$, the codnition $c_{i,j}=u_i+v_j$ is always true (that always $c_{i,j}^{\prime }=0$).

The $c^{\prime }$ is called the reduction of a cost.

In general, the constraint that is made is $c_{i,j}\ge u_i+v_j$ (not just equal) (i.e. $c_{i,j}^{\prime }\ge 0$ whenever $x_{i,j}=0$ this is because…

We want to choose the dual variables in such way that when with these constraints, choosing these values will ensure that there exist a perfect matching (all the cells where the matching happens $c^{\prime }=0$). So the total cost in a reduces sense, of a perfect matching is $0$ or the total cost of a perfect matching is the sum of Ui and sum of Vj as everything else is a 0.

• So the first term is 0 whether or not there is an assignment or not.
• In general, however, when $x_{i,j}=0$, although we dont care for the first term, we have to insist that $c_{i,j}\ge u_i+v_j$ ($c_{i,j}^{\prime }\ge 0$)

If this is the case, we can transform our problem from minimising cost to :

Find a perfect matching (of size N) that maximizes

$z={\sum }_{i=1}^N{u}_i+{\sum }_{j=1}^N{v}_j$

because the first term has disappeared no matter what.

subject to the constraints: ui + vj≤ci,j ∀1 ≤ I ≤ N, 1 ≤ j ≤ N

Note how it mentions for all I and j, because as soon as we choose ui and vj, then it effects all I and j, so that we shouldn’t greedily choose but more intentionally.

But why is it maximisation?

Why Is It Equivalent? Why Is The Dual Formulation Legit?

Let M′ be any feasible (as per the above constraints) perfect matching (i.e. |M′ | = N). The total cost of the assignments in M′ is:

• If we add up the cost of all possible assignments
  • X ∀xi,j=1∈M′ ci,j
• Because cij is greater than or equal to each ui + vj then the summation holds the same
  • X ∀xi,j=1∈M′ ci,j ≥ X ∀xi,j∈M′ ui + vj
• So the total cost is greater than or equal to the sum of ui + vj
• This can be rewritten as
  • cost(M′ ) ≥ X N I=1 ui + X N j=1 vj
• So the cost of any matching is an upper bound of the sum of the row + column variables
• The above makes PN I=1 ui + PN j=1 vj a lower bound to the cost of any feasible matching
• Thus a perfect matching M such that cost(M) = X N I=1 ui + X N j=1 vj ≤ cost(any feasible M′ ) …has to be optimal (i.e. min-cost overall feasible matchings) of M when the strict equality is achieved!

The Hungarian Algorithm (Cost-Matrix Reduction Method)

Example

step 1 find feasible values of ui (starting value) step 2 find feasible value of vj (starting value) step 3 can I find an assignment of variables step 4

stop when size of matching = N (perfect matching)

Input: An $N\times N$ cost matrix. Output: A perfect matching (i.e., $N$ agent-task assignments) with minimum total cost.

Example Cost Matrix ( $N=5$ ):

	Task 1	Task 2	Task 3	Task 4	Task 5
Agent 1	11	7	10	17	10
Agent 2	13	21	7	11	13
Agent 3	13	13	15	13	14
Agent 4	18	10	13	16	14
Agent 5	12	8	16	19	10

Algorithm Overview:

• Step 1: Initialize dual variables $u_i$.
• Step 2: Initialize dual variables $v_j$.
• Remaining steps: Iteratively find valid assignments and update $u_i$, $v_j$ until a perfect matching is achieved.

Note: In later steps, agent and task labels are omitted for simplicity.

Step 1: Row Reduction

Goal: Begin with a feasible set of $u_i$ values.

Procedure: For each row in the cost matrix, find the minimum value and subtract it from every element in that row. This is equivalent to initializing:

$$u_i=\min ({\text{row}}_i)$$

Row Minima: $u_1=7,u_2=7,u_3=13,u_4=10,u_5=8$

Result after Row Reduction:

Remember addition/subtraction by a constant across the entire row/column does not effect the results. Also note that $c_{i,j}^{\prime }$ is not tracked but instead calculated. Additioanlyl you can assume that $u_i$ and $v_j$ is initially 0 instead of -

Hungarian method – Step 2 (…and a feasible set of vj values In the resultant matrix, for each column, find the column minimum and subtract it from every element of that column. Initialize vj = min(colj ).

Assign the minimum values as your ui and vj values are important because they give you the first feasible value, u can’t have a value less than this. (any other expalanation for this step?)

Additionally, you dont actually need the entire table, you only need the initial values and the cost matrix, because remember, by subtracting the minimum from the values, what we are doing is calculating $c_{i,j}^{\prime }=c_{i,j}-u_i-v_j$ so it can be calculated via the cost matrix.

Look at $c_{5,3}^{\prime }$ in the new table, it is equal $c_{5,3}^{\prime }=c_{5,3}-u_5-v_3=16-8-0=8$

Does the order matter?

Hungarian Method – Step 3: Make Assignments On Zeroes

Once the cost matrix has been reduced, the goal is to start assigning agents to tasks using the zero-valued cells (which represent potential optimal matches after reductions).

Step 3.1 – Row-wise Assignment

For each row:

• If a row contains only one zero, assign that agent to the corresponding task (i.e., set $x_{i,j}=1$).
• Once a task is assigned, cross out all other zeroes in that task’s column to prevent conflicting assignments.
• If a row contains multiple zeroes, skip it for now.

This step helps make as many conflict-free assignments as possible by scanning rows.

Step 3.2 – Column-wise Assignment

Repeat the logic, now scanning columns instead of rows:

• For each column, if there is only one zero, assign that task to the corresponding agent (i.e., set $x_{i,j}=1$).
• Then, cross out all other zeroes in that agent’s row to avoid multiple assignments.
• Skip columns that have multiple zeroes.

This helps identify more valid matches and builds on the progress from Step 3.1.

At the end of Step 3, count the number of successful assignments made (i.e., size of the current matching). If the number of assignments equals $N$, you’re done. Otherwise, proceed to the next step of the algorithm.

The Hungarian Algorithm (Cost-Matrix Reduction Form)

Step 1: Row Reduction

Given an $N\times N$ cost matrix $C=[c_{ij}]$, begin by initializing a set of dual variables $u_i$ for each row. These dual variables help define a feasible labeling for the problem and guide the construction of the equality graph, where edges have zero reduced cost.

For each row $i$, compute the minimum value in that row:

$$u_i=\underset{j}{\min }{c}_{ij}$$

Subtract $u_i$ from every entry in row $i$. This operation guarantees that each row will contain at least one zero. Importantly, the relative differences between entries in a row are preserved, maintaining the structure of the assignment costs while reducing absolute values.

After this operation, we obtain a new matrix $C^{\prime }=[c_{ij}^{\prime }]$, where:

$$c_{ij}^{\prime }=c_{ij}-u_i$$

The zero entries in $C^{\prime }$ correspond to edges in the initial equality graph—these are candidate assignments where the cost has been reduced to zero under the current labeling.

Step 2: Column Reduction

With the row-reduced matrix $C^{\prime }$, proceed to reduce the columns to ensure that every column also contains at least one zero. This further densifies the equality graph by potentially introducing new zero entries.

For each column $j$, compute:

$$v_j=\underset{i}{\min }{c}_{ij}^{\prime }$$

Subtract $v_j$ from each entry in column $j$, yielding the final reduced cost matrix $C^{\prime \prime }=[c_{ij}^{\prime \prime }]$:

$$c_{ij}^{\prime \prime }=c_{ij}-u_i-v_j$$

This operation ensures that each column also has at least one zero. The dual variables $v_j$ are initialized in this step. The resulting matrix $C^{\prime \prime }$ defines an equality graph where an edge $(i,j)$ exists if and only if $c_{ij}^{\prime \prime }=0$, which is equivalent to the condition $c_{ij}=u_i+v_j$.

At this point, the algorithm will attempt to find a perfect matching within the equality graph.

Step 3: Initial Matching

The goal in this step is to find an initial feasible matching—a set of one-to-one assignments—within the equality graph constructed from zero entries in the reduced cost matrix.

Step 3.1: Row-Based Assignment

Start by scanning each row of the reduced matrix. If a row contains exactly one zero that has not been crossed out or previously assigned, make an assignment by matching that row (agent) to the corresponding column (task). Once this assignment is made:

• The assigned cell is marked as part of the tentative matching.
• All other zero entries in the same column are crossed out, as no other agent can now be assigned to that task.

This greedy process locks in unambiguous assignments and simplifies the problem by reducing the number of free zeros in the matrix. If a row has multiple zeros, skip it for now and revisit it later.

Step 3.2: Column-Based Assignment

Next, apply a similar process to the columns. For each column that contains exactly one uncrossed zero, make an assignment between the corresponding task and agent. Once the assignment is made:

• The selected cell is marked as part of the matching.
• All other zero entries in the same row are crossed out.

This column-wise pass complements the earlier row-wise assignments and can increase the number of unique matchings found in this stage.

After completing both steps, we now have a tentative matching $M$. If the number of matched pairs $|M|=N$, then a perfect matching has been found, and the algorithm can proceed to the final step. If not, we continue with refining the equality graph.

Step 3.3: Prepare To Improve Matching (Marking Process)

If the current matching $M$ is incomplete (i.e., $|M|<N$), we initiate a process to improve the labeling by identifying a minimum vertex cover in the equality graph. This is done through a marking process as follows:

1. Mark all unassigned rows—these represent agents not yet matched to any task.
2. For each marked row, examine all zero entries. For each such entry $(i,j)$, mark the corresponding column $j$.
3. For each marked column, if it contains an assigned zero (i.e., one that is part of the current matching), mark the row that made the assignment.
4. Repeat steps 2 and 3 until no new rows or columns can be marked.

At the end of this marking process, draw lines through all unmarked rows and marked columns. These lines collectively cover all zeros in the matrix that participate in the equality graph. According to Kőnig’s theorem, the number of lines used equals the size of the current maximum matching.

This process isolates the structure that prevents a perfect matching and prepares the way for updating the cost matrix and labels to introduce new zero entries.

Step 4: Update Labeling And Cost Matrix

If a perfect matching has not yet been achieved, we update the dual variables and the cost matrix to introduce new zeros into the equality graph.

1. Identify the minimum uncovered value $\theta$ among all entries that are not covered by any line from the previous step.

2. Update the dual variables:

   • For every unmarked row $i$, update $u_i\leftarrow u_i+\theta$.
   • For every marked column $j$, update $v_j\leftarrow v_j-\theta$.

3. Leave all other dual variables unchanged.

These updates preserve the dual feasibility conditions and maintain the complementary slackness necessary for optimality. They also create at least one new zero in the matrix, increasing the number of edges in the equality graph and offering a greater chance of finding a perfect matching in the next iteration.

The reduced cost matrix $C^{\prime \prime }$ is updated accordingly, and the algorithm returns to Step 3 to attempt matching again with the enriched equality graph.

Step 5: Repeat Matching

Repeat the matching process described in Step 3 using the newly updated cost matrix. Continue iterating between Steps 3 and 4 until a perfect matching is found (i.e., $|M|=N$).

Once a perfect matching is obtained, extract the assignments directly from the final matching $M$. The total cost of the optimal assignment can be computed in one of two equivalent ways:

$$\text{Total cost}=\sum _{(i,j)\in M}{c}_{ij}$$

Alternatively, since the algorithm maintains dual feasibility and complementary slackness throughout, the total cost is also equal to the sum of the dual variables:

$$\text{Total cost}=\sum _{i=1}^N{u}_i+\sum _{j=1}^N{v}_j$$

This concludes the algorithm. The final result is a perfect matching of agents to tasks with minimum total cost.