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.