## 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 t_{1 }, t_{2}, ... , t_{n} .

(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* + t_{max} where t_{max} 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 p_{e} 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) w_{e} > w_{f} 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.