Consider the Load Balancing Problem from Section. Some friends of yours are running a coll...

Consider the Load Balancing Problem from Section. Some friends of yours are running a collection of Web servers, and they've designed a local search heuristic for this problem, different from the algorithms described in Chapter.

Recall that we have m machines M1,… , Mm, and we must assign each job to a machine. The load of the ith job is denoted ti. The makespan of an assignment is the maximum load on any machine:

Your friends' local search heuristic works as follows. They start with an arbitrary assignment of jobs to machines, and they then repeatedly try to apply the following type of "swap move."

Let A(i) and A(j) be the jobs assigned to machines Mi and Mj, respectively. To perform a swap move on Mi and Mj, choose subsets of jobs B(i) ⊆ A(j) and B(j) ⊆ A(j), and "swap" these jobs between the two machines. That is, update A(i) to be A(i) ⋃ B(j) - B(i), and update A(j) to be A(j) ⋃ B(i) - B(j). (One is allowed to have B(i) = A(i), ortohave B(i) be the empty set; and analogously for B(j).)

Consider a swap move applied to machines Mi and Mj. Suppose the loads on Mi and Mj before the swap are Ti and Tj, respectively, and the loads after the swap are T[ and Tj. We say that the swap move is improving if  —in other words, the larger of the two loads involved has strictly decreased. We say that an assignment of jobs to machines is stable if there does not exist an improving swap move, beginning with the current assignment.

Thus the local search heuristic simply keeps executing improving swap moves until a stable assignment is reached; at this point, the resulting stable assignment is returned as the solution.

Example. Suppose there are two machines: In the current assignment, the machine M1 has jobs of sizes 1, 3, 5, 8, and machine M2 has jobs of sizes 2, 4. Then one possible improving swap move would be to define B(1) to consist of the job of size 8, and define B(2) to consist of the job of size 2. After these two sets are swapped, the resulting assignment has jobs of size 1, 2, 3, 5 on M1, and jobs of size 4, 8 on M2. This assignment is stable. (It also has an optimal makespan of 12.)

(a) As specified, there is no explicit guarantee that this local search heuristic will always terminate. What if it keeps cycling forever through assignments that are not stable?

Prove that, in fact, the local search heuristic terminates in a finite number of steps, with a stable assignment, on any instance.

(b) Show that any stable assignment has a makespan that is within a factor of 2 of the minimum possible makespan.