Algorithm Design Techniques
Due: Thurs, April 10, in class.
This assignment is optional.
If you hand it in, each assignment will be worth 4pts each.
If you don't hand it in, the other 4 assignments will be worth 5 pts
If you work closely with someone else, indicate the person's name(s)
on your homework.
The final write-up of each assignment must, however, be your own work.
1. Consider the machine
scheduling (Load Balancing) problem with m jobs and integer
running times t1 , t2, ... , tn .
(a) Let T be the finish time of the latest job, assuming jobs are
scheduled by the List heuristic (Greedy-Balance, P. 601).
Let T* be the length of the shortest schedule.
Show T <= T* + tmax where tmax is the largest
of the running times.
(b) Construct an example for the list decreasing (Sorted Balance, P.
605) heuristic with m=3, n=7 achieving the upper bound
T/T* <= 11/9 that we proved in class.
Read Section 11.4, the Pricing Method.
(a) Write down the dual of the LP-relaxation of the integer program for
weighted vertex cover VC.IP on P. 634.
(To get the LP-relaxation, replace the integrality condition by
non-negativity for each variable.)
(b) Show that the variables pe obtained from
Vertex-Cover-Approx on P. 621 gvie a feasible solution for the
dual you found in 2(a).
(c) Use 2(b) to show that (11.13) on P. 620 follows from the weak
duality theorem for linear programming.
3. Get G=(V,E) be a
connected graph with positive edge weights, such that each edge weight
Let T be any spanning tree in G. We try to find a minimum weight
spanning tree by using local search as follows:
Start with T and see try to find an edge e in T and an edge f that is
not in T such that
(i) we > wf and (ii) T-e+f is a tree (ie.
adding f and deleting e gives a new spanning tree with smaller weight).
If there are such edges e and f, continue the local search with the
If there are no such edges, stop.
Show that this local search in fact always finds the minimum weight
Hint: Review problem 3 of Assignment 1.