CMSC 435 Algorithm Analysis & Design

Answers to Homework # 6

1. Order the jobs by decreasing penalty. Create an array, sched, indexed from 0 to n-1 where n is the number of jobs to be scheduled. If a job has a deadline to t_i, it must be scheduled into one of the time slots 0 .. t_i-1 in sched if it is not to incur a penalty. The strategy for this algorithm will be to schedule each job removed from the ordering in the latest available time slot that does not incur a penalty. If none are available, put the job in a collection of jobs to be scheduled wherever possible once all of the jobs in the ordering have been examined. Since the number of time slots is equal to the number of jobs, all jobs will be scheduled. We can prove that the greedy algorithm will give us a schedule with the minimum total penalty. Let J_i be a job that cannot be scheduled before its deadline and incurs a penalty. Assume there is an alternate schedule S’ in which J_i is not penalized. That means that J_i will replace some other job J_k in the previous schedule. But since J_k had to have been scheduled before J_i originally for J_i not to have found an available time slot before it would be penalized, J_k must have had a penalty >= the penalty for running J_i late. Therefore the schedule S’ must produce a penalty >= the total penalty produced by the original schedule S. Here is a greedy algorithm for this unit-time scheduling problem. Let H be a max-ordered heap ordered by penalty; let J be an array of n Job objects; let sched an array indexed by time-slot that holds the schedule of jobs; let P = the total penalty; and let Stk be a stack for holding jobs that cannot be scheduled without penalty.

Algorithm minPenalty(Job[] J) produces a schedule and a total penalty

Heap H = new Heap(J) //uses buildHeap constructor O(n)

Job sched = new Job[n]

Double P = 0.0;

Stack Stk = new Stack()

While (!H.isEmpty()) {

Job jb = H.deletmax()

Int t = jb.deadline – 1;

While (t >= 0 && sched[t] != null)

t--;

if (t >= 0)

sched[t] = jb;

else

Stk.push(jb);

P = P + jb.penalty

endWhile // worst case O(n²)

int j = n - 1

While (!Stk.isEmpty())

Job jbx = Stk.pop())

While (sched[j] != null)

j--;

endWhile // worst case O(n)

end

2. (Kleinberg & Tardos Chapter 4 # 5) Let L be a listing of the locations of each of the houses in order from east to west. Let S be a Stack containing tower placements. Start from the west and let pos be the position of the first house encountered. Set pos = pos – 4 and push this value onto the stack – the location of the last cell tower. Delete all of the house locations within 4 miles of pos from the listing and repeat the above. Continue with this strategy until there are no houses left in the list or pos = 0.

3. (Kleinberg & Tardos Chapter 4 # 24) Let v be the root and v’ and v” its left and right child respectively. Let d’ be the maximum root to leaf distance for all roots that are descendants of v’ and d” the corresponding distance for all roots that are descendants of v”. Then if (d’ > d”) we add the difference (d’- d”) to the edge from v to v”. Else, if (d” > d’) we add the difference (d”- d’) to the edge from v to v’. If d” = d’ we leave both edge distances unchanged. Then we recursively apply this procedure to v’ and v”. Now we prove that this procedure produces the optimal solution to this problem. Lemma 1: Let w be an internal node in T, and let e’ and e” be two edges directly below w. If a solution adds non-zero length to both e’ and e”, then it is not optimal. Proof: Suppose that δ’ >0 and δ” > 0 are added to the length of each edge respectively.. Let δ = min(δ’, δ”). Then a solution which adds δ’ – δ and δ” – δ to the lengths of these two edges must also have zero skew and uses less total length. Lemma 2: Let w be a node in T that is neither the root nor a leaf. If a solution increases the length of every path from w to a leaf below w, then the solution is not optimal. Proof: Suppose that x₁, …, x_k are the leaves below w. Consider edges e in the subtree below w with the following property: the solution increases the length of e and it does not increase the length of any edge on the path from w to e. Let F be the set of such edges. We observe two facts about F. First, for each leaf x_i, the first edge on the w-x_i path whose length has been increased must belong to F, and no other edge on this path can belong to F. Thus there is exactly one edge from F on every w-x_i path. Second |F| >= 2, since a path in the left subtree below w shares no edges with a path in the right subtree below w, and yet each contains an edge of F. Let e_w be the edge entering w from its parent. Let δ be the minimum amount of length added to any of the edges in F. If we subtract δ from the length added to each edge in F, and add δ to the edge above w, the length of all root paths remains the same, and so the tree remains zero-skew. But we have subtracted |F| δ >= 2 δ from the total length of the tree and added only δ, so we get a zero skew tree with less total length. Theorem: The Deferred Merge Embedding algorithm described above produces the unique optimal solution. Proof: Consider any other solution and let v be any node of T at which the solution does not add lengths in the way that DME would. Using the previous notation, we assume without loss of generality that d’ > d”. Suppose the solution adds δ’ to the edge (v, v’) and δ” to the edge (v, v”). If δ” – δ’ = d’ – d”, then it must be that δ’ > 0 or else the solution would do the same thing as DME; in this case by Lemma 1 it is not optimal. If δ” – δ’ < d’ – d”, then the solution will still have to increase the length of the path from v” to each of its leaves in order to make the tree zero-skew; so by Lemma 2 it is not optimal. Similarly, if δ” – δ’ > d’ – d”, then the solution will still have to increase the length of the path from v’ to each of its leaves in order to make the tree zero-skew, so again it is not optimal.