Hungarian algorithm: Difference between revisions

Revision as of 05:23, 14 May 2023

Revision as of 05:33, 14 May 2023

Line 108:

==The algorithm in O(n^3) time==

Suppose there are <math>J</math> jobs and <math>W</math> workers (<math>J\le W</math>). We describe how to compute for each prefix of jobs the minimum total cost to assign each of these jobs to distinct workers. Specifically, we add the <math>j</math>th job and update the total cost in time <math>O(jW)</math>, yielding an overall time complexity of <math>O\left(\sum_{j=1}^JjW\right)=O(J^2W)</math>. Note that this is much better than <math>O(W^3)</math> when the number of jobs is small relative to the number of workers.

===Adding the j-th job in O(jW) time===

Line 114:

We use the same notation as the previous section, though we modify their definitions as necessary. Let <math>S_j</math> denote the set of the first <math>j</math> jobs and <math>T</math> denote the set of all workers.

Before the <math>j</math>th step of the algorithm, we assume that we have a matching on <math>S_{j-1}\cup T</math> that matches all jobs in <math>S_{j-1}</math> and potentials <math>y</math> satisfying the following condition: the matching is tight with respect to the potentials, and the potentials of all unmatched workers are equalzero, and at least the maximumpotentials potential overof all matched workers are non-positive. Note that such potentials certify the optimality of the matching.

During the <math>j</math>th step, we add the <math>j</math>th job to <math>S_{j-1}</math> to form <math>S_j</math> and initialize <math>Z=\{j\}</math>. At all times, every vertex in <math>Z</math> will be reachable from the <math>j</math>th job in <math>G_y</math>. While <math>Z</math> does not contain a worker that has not been assigned a job, let

Line 199:

// delta will always be non-negative,

// except possibly during the first time this loop runs

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

for (int w = 0; w <= W; ++w) {

if (in_Z[w]) ys[job[w]] += delta, yt[w] -= delta;

Line 262:

}

</syntaxhighlight>

==Connection to successive shortest paths==