Hungarian algorithm: Difference between revisions

Revision as of 06:33, 9 April 2024

Revision as of 20:50, 31 May 2024

Line 55:

=== Matrix formulation ===

In the matrix formulation, we are given a nonnegativean ''n''×''n'' [[Matrix (mathematics)|matrix]], where the element in the ''i''-th row and ''j''-th column represents the cost of assigning the ''j''-th job to the ''i''-th worker. We have to find an assignment of the jobs to the workers, such that each job is assigned to one worker and each worker is assigned one job, such that the total cost of assignment is minimum.

This can be expressed as permuting the rows of a cost matrix ''C'' to minimize the [[Trace (linear algebra)|trace]] of a matrix,

Line 68:

=== Bipartite graph formulation ===

The algorithm can equivalently be described by formulating the problem using a bipartite graph. We have a [[complete bipartite graph]] <math>G=(S, T; E)</math> with {{mvar|n}} worker vertices ({{mvar|S}}) and {{mvar|n}} job vertices ({{mvar|T}}), and the edges ({{mvar|E}}) each have a nonnegative cost <math>c(i,j)</math>. We want to find a [[perfect matching]] with a minimum total cost.

==The algorithm in terms of bipartite graphs==

Line 197:

}

}

// delta will always be non-negativenonnegative,

// except possibly during the first time this loop runs

// if any entries of C[j_cur] are negative

Line 357:

===Step 1===

'''For each row, its minimum element is subtracted from every element in that row.''' This causes all elements to have non-negativenonnegative values. Therefore, an assignment with a total penalty of 0 is by definition a minimum assignment.

This also leads to at least one zero in each row. As such, a naive greedy algorithm can attempt to assign all workers a task with a penalty of zero. This is illustrated below.