Content deleted Content added
→The algorithm in O(n^3) time: title in math tag |
→Adding the j-th job in O(jW) time: title in math tag |
||
Line 110:
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 <math>O(jW)</math> 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.
| |||