Content deleted Content added
m remove math from headings |
m minor improvements to →Adding the j-th job in O(jW) time |
||
Line 112:
===Adding the j-th job in O(jW) time===
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 equal and at least the maximum potential over all matched workers. 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
:<math>\Delta := \min\{c(j, w)-y(j)-y(w):j\in Z\cap S_j, w\in T\setminus Z\}</math>
and <math>w_{\text{next}}</math> denote any <math>w</math> at which the minimum is attained. After adjusting the potentials in the way described in the previous section, there is now a tight edge from <math>Z</math> to <math>w_{\text{next}}</math>.
| |||