CSC373 Fall’20 Tutorial 2 Solutions Tue. Sept. 22, 2020
Q1 Interval Scheduling on m Machines
Let us recall the interval scheduling problem from class. We are given n jobs, where each job Ij = [sj,fj) is an interval. Two jobs are compatible if their intervals have empty intersection. In class, we saw how to schedule a maximum number of mutually compatible jobs on one machine: consider the jobs one-by-one in an increasing order of their finish time (EFT), and greedily pick the job being considered if it is compatible with the ones picked so far.
Now, suppose that we have m machines available instead of just one. A feasible schedule can be thought of as a mapping σ : {1,…,n} → {0,1,…,m}, where job Ij is assigned to machine k if σ(j) = k > 0, and unassigned if σ(j) = 0. Jobs scheduled on any single machine must still be mutually compatible. Subject to that, we want to maximize the number of jobs scheduled, i.e., |{j ∈ {1,…,n} : σ(j) > 0}|.
(a) Consider the following Earliest Start Time (EST) algorithm. Algorithm 1: m-ISP-EST
1 2 3 4 5 6 7 8
Sort the jobs in an increasing order of their start time so that s1 ≤ . . . ≤ sn forj=1,…,ndo
if there is a machine k such that all jobs assigned to it are compatible with Ij then Assign job Ij to any such machine k
else
Let job Ij remain unscheduled end
end
Consider the following attempt to prove optimality of this algorithm.
1. Consider any job Ij that the algorithm does not schedule.
2. At that point, each machine must have a job scheduled that conflicts with Ij.
3. As seen in class, all m conflicting jobs must have start time earlier than sj (due to the EST
order) and finish time after sj (since they conflict with Ij).
4. Hence, there are at least m + 1 jobs that all contain time sj in their intervals.
5. Since there are only m machines, even the optimal algorithm must drop at least one of them.
6. The optimal algorithm drops a job for every job dropped by our EST algorithm. Hence, our
EST algorithm schedules the maximum number of jobs.
Which step(s) of the argument above are flawed, and why?
(Solution to (a)) The sixth step is flawed. We would need to show that for every job dropped by the EST algorithm, the optimal solution drops a distinct job. Otherwise, the optimal solution may drop one job that conflicts with two or more jobs dropped by the EST algorithm, thus leading to more jobs scheduled.
1
(b) Next, consider the Earliest Finish Time (EFT) algorithm. Algorithm 2: m-ISP-EFT
1 2 3 4 5 6 7 8
Sort the jobs in an increasing order of their finish time so that f1 ≤ . . . ≤ fn forj=1,…,ndo
if there is a machine k such that all jobs assigned to it are compatible with Ij then Assign job Ij to any such machine k
else
Let job Ij remain unscheduled end
end
Prove that this algorithm does not always yield an optimal solution by producing a counterexample.
(Solution to (b)) Consider an instance with m = 2 and four jobs: I1 = [1,3), I2 = [2,4), I3 = [4, 5), and I4 = [3, 6). Note that these are sorted by EFT. The EFT algorithm schedules the first two jobs on two different machines. In the third round, it has a choice to schedule I3 on either machine. If it ends up scheduling it on the same machine as I1, then I4 will have to be dropped. This would be suboptimal because scheduling all four jobs — I2 and I3 on one machine and I1 and I4 on the other — is feasible.
(c) Finally, consider the EFT algorithm, but with a smart tie-breaking in case there are multiple machines which can accommodate job Ij.
Algorithm 3: m-ISP-EFT-Best-Fit
1 2 3 4 5
6 7 8 9
10
Sort the jobs in an increasing order of their finish time so that f1 ≤ . . . ≤ fn forj=1,…,ndo
Let S be the set of machines such that all jobs assigned to them are compatible with Ij if S̸=∅then
For each machine k ∈ S, let ek be the greatest finish time of any job assigned to it so far
Assign job Ij to machine k ∈ S with the greatest ek else
Let job Ij remain unscheduled end
end
Prove that this algorithm always yields an optimal solution. Design an efficient implementation and analyze its worst-case running time.
(c) Correctness: Let Gi be the greedy schedule after the first i intervals have been processed. We prove by induction on i that for each i ∈ {0, 1, . . . , n}, there exists an optimal schedule OP Ti that extends Gi — that is, matches Gi on the scheduling of jobs I1 through Ii. This shows that Gn is optimal.
The base case of i = 0 trivial: since G0 = ∅, any optimal solution OPT0 extends it. Suppose the inductive hypothesis holds for i − 1. We prove it for i by considering the following cases:
2
• Ii is dropped in Gi. This implies that no extension of Gi−1 can schedule Ii on any machine. In particular, OPTi−1 cannot schedule Ii either. Thus, OPTi−1 extends Gi as well.
• Ii is scheduled on the same machine in Gi and in OPTi−1. Then, clearly OPTi−1 again extends Gi.
• Ii is scheduled on some machine k in Gi, but is dropped in OPTi−1. Let Ij (with smallest j > i) be the next interval scheduled on machine k under OPTi−1. Note that such an interval must exist, otherwise, by scheduling Ii on machine k under OPTi−1, we could schedule one extra job, which would contradict optimality of OPTi−1. Define OPTi by replacing the interval Ij with Ii in OPTi−1. To see why this is feasible, suppose ek is the latest finish time of any job scheduled on machine k before job i. This quantity is the same under Gi−1 and OPTi−1 because the latter extends the former. Because Gi extends Gi−1 by scheduling Ii on machine k, we must have ek ≤ si, and because OPTi−1 extends Gi−1 by scheduling job j next on machine k, the machine is available until fj after removing job Ij. Since j > i, we have fj ≥ fi. So Ii can be scheduled on machine k. Note that replacing job j with i keeps the schedule optimal.
• Ii is scheduled on some machine k in Gi, and some different machine k′ in OPTi. Construct OPTi by starting with OPTi−1, and swapping the schedules of machines k and k′ after time si. That is, for all jobs j ≥ i, if Ij is scheduled on machine k (resp. k′), then we move it to machine k′ (resp. k).
For an efficient implementation, we note that we only need the latest finish time on each machine, which we can keep track of easily because it is always the finish time of the last job scheduled on the machine under the EFT order. The key step is to search for the maximum latest finish time that does not exceed the start time of the job under consideration. The following implementation uses binary search trees (BST) to do this efficiently.
Algorithm 4: m-ISP-EFT-Best-Fit
1 2 3 4 5 6 7 8 9
10
Sort the jobs in an increasing order of their finish time so that f1 ≤ . . . ≤ fn Create a BST of the m machines using key ek ← 0 for each machine k forj=1,…,ndo
Search the BST for the greatest key that is less than or equal to si if there is no such key then
Let job Ij remain unscheduled else
If the key corresponds to machine k, schedule Ij on k and update its key ek ← fj end
end
This algorithm spends O(logm) time in each iteration of the for loop, so its worst-case running time is O(n log m + m), where the latter term is for creating the BST of size m in the first place.
3
Q2 Cops and Robbers
You are given an array A[1, . . . , n] with the following specifications:
• Each element A[i] is either a cop (’c’) or a robber (’r’).
• A cop can catch any robber who is within a distance of K units from the cop, but each cop can catch at most one robber.
Write an algorithm to find the maximum number of robbers that can be caught.
Solution to Q2
Algorithm 5: Cops-and-Robbers
1 2 3
4
5 6
for c = 1,…,n do
if A[c] is a cop then
Find the smallest index r in [c−K,c+K] such that A[r] is a robber who is not currently assigned to any cop
If such an index r exists, assign cop A[c] to catch robber A[r], else let cop A[c] be unassigned
end end
Correctness: Suppose for contradiction that this algorithm is not optimal. Let G denote the greedy assignment it produces. Let OPT be an optimal solution that matches G for as many iterations as possible. That is, for some k, OPT assigns the first k cops exactly the same way as G does, and there is no optimal solution which matches G on the first k + 1 cops. Because G is not optimal, k is less than the number of cops.
We derive a contradiction by proving that there is an optimal solution OPT′ which matches G on the first k + 1 cops. Let c denote the index of the k + 1th cop. We consider the following cases:
1. Suppose G leaves cop A[c] unassigned, while OPT assigns cop A[c] to robber A[r]. In this case, r ∈ [c−K,c+K]. However, since OPT matches G on the first k cops, A[r] must not be assigned to the first k cops under G. This is a contradiction as the greedy algorithm would not have left cop A[c] be unassigned in that case.
2. Suppose G assigns cop A[c] to some robber A[r], while OPT leaves cop A[c] unassigned. If A[r] is not assigned to any cop under OPT, then we have a contradiction as assigning A[c] to A[r] would increase the quality of the solution. Hence, A[r] must be assigned to some other cop A[c′] under OPT. In this case, we can create OPT′ by assigning A[c] to A[r] and leaving A[c′] unassigned.
3. Suppose G assigns cop A[c] to some robber A[r], while OPT assigns cop A[c] to some other robber A[r′]. If A[r] is not assigned to any cop under OPT, then we can create OPT′ by switching the assignment of A[c] from A[r′] to A[r]. If A[r] is assigned to some cop A[c′] under OPT, then we create OPT′ by switching the assignments of A[c] and A[c′], i.e., by assigning A[c] → A[r] and A[c′] → A[r′]. For this to work, we need to argue that A[c′] → A[r′] is a valid assignment, i.e., that r′ ∈ [c′ − K, c′ + K].
4
Because OPT and G match on the assignment of the first k cops, we have c′ > c. Further, because G greedily assigns cop A[c] to the first feasible robber not assigned to any previous cops, we have r′ > r. Now, because OPT assigns A[c′] to A[r], we have c′ −K ≤ r ≤ r′. On the other hand, because OP T also assigns A[c] to A[r′], we also have r′ ≤ c + K ≤ c′ + K. This completes the proof of validity of A[c′] → A[r′] assignment.
Running Time: The above algorithm clearly runs in time O(nK) because for each of O(n) cops, it searches for the first available feasible robber in O(K) time. However, the running time can be reduced to O(n) by keeping track of two indices c and r for the next available cop and robber, and increasing both when a match is made or the minimum when they are too far, as the algorithm below shows.
Algorithm 6: Cops-and-Robbers
1 2 3 4 5 6 7 8 9
10 11
Initialize c and r to the indices of the first cop and the first robber, respectively whilecandrarenotnulldo
if |c−r|≤K then
Assign cop c to catch robber r
Increment both c and r to the indices of the next cop and robber, respectively
else if c