CSC373 Fall’20 Tutorial 2 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?
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. (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.
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.
2