Algorithm Design Techniques

 COMP-360              Assignment 5         Due: Thurs,  April 10,  in class.
No late assignments.

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 each.

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.

2.  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 is unique.
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 tree T-e+f.
If there are no such edges, stop.

Show that this local search in fact always finds the minimum weight spanning tree.
Hint: Review problem 3 of Assignment 1.