Content deleted Content added
Neutronstar2 (talk | contribs) No edit summary |
Replace <nowiki><math></nowiki> tags in section headers (see MOS:HEAD) |
||
Line 106:
To show that {{mvar|y}} remains a potential after being adjusted, it suffices to show that no edge has its total potential increased beyond its cost. This is already established for edges in {{mvar|M}} by the preceding paragraph, so consider an arbitrary edge {{mvar|uv}} from {{mvar|S}} to {{mvar|T}}. If <math>y(u)</math> is increased by {{math|Δ}}, then either <math>v \in Z \cap T</math>, in which case <math>y(v)</math> is decreased by {{math|Δ}}, leaving the total potential of the edge unchanged, or <math>v \in T \setminus Z</math>, in which case the definition of {{math|Δ}} guarantees that <math>y(u)+y(v)+\Delta \leq c(u,v)</math>. Thus {{mvar|y}} remains a potential.
==The algorithm in
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 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
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.
| |||