Approximation Algorithms: Greedy Load Balancing/Vertex Cover

[nrobidoux]

Homework Statement

You are asked to consult for a business where clients bring in jobs each day for processing. Each job has a processing time t_i that is known when the job arrives. The company has a set of ten machines, and each job can be processed on any of these ten machines.

At the moment the business is running the simple Greedy-Balance Algorithm we discussed in Section 11.1. They have been told that this may not be the best approximation algorithm possible, and they are wondering if they should be afraid of bad performance. However, they are reluctant to change the scheduling as they really like the simplicity of the current algorithm: jobs can be assigned to machines as soon as they arrive, without having to defer the decision until later jobs arrive.

In particular, they have heard that this algorithm can produce solutions with makespan as much as twice the minimum possible; but their experience with the algorithm has been quite good: They have been running it each day for the last month, and they have not observed it to produce a makespan more than 20 percent above the average load, 1/10 * sum(t_i, i = 1..n).

To try understanding why they don’'t seem to be encountering this factor-of-two behavior, you ask a bit about the kind of jobs and loads they see. You find out that the sizes of jobs range between 1 and 50, that is, 1 <= t_i <= 50 for all jobs i; and the total load sum(t_i, i = 1 .. n); is quite high each day: it is always at least 3,000. Prove that on the type of inputs the company sees, the Greedy-Balance Algorithm will always find a solution whose makespan is at most 20 percent above the average load.

Add on:
Create an application scenario where the problem can be formulated as Vertex Cover Problem. Use a small problem instance of this application problem as input to illustrate how the approximation algorithm using pricing method Vertex-Cover-Approx(G, w) described in Section 11.4 works and show the solution. Find the optimal solution yourself, and compare it with the solution found by the approximation algorithm.

Homework Equations

Greedy Load Balancing: when a new job with load x _i arrives it is assigned to machine with smallest load.

Vertex Cover: Given graph G with nodes {V}, vertex cover is a subset of V such that all edges in the graph have at least 1 part in the subset.

3. The Attempt at a Solution
Right now I'm more curious about the instructor's addition... (and after much thought while this sat open I'll go back to the original problem until I get some clarification from the professor.)

I'm curious how the 20% is arrived at. I basically took the minimum total load of 3000 and distributed it among all machines, minus 1 job. Worst case all jobs up to this point have a load of 1. This leaves me with 9 machines at 300 and one at 299. If I add a job of 50 to that machine it has a load of 349. 349/300 = 1.16333333333 not 1.2 times the average.

I could say that prior to submission of the last job, 9 machines had a load of 300 and 1 had a load of 250... but 250 is not the average load, 300 is.

 

[nilesh_pat]

So I can't be sure what the professor is asking us to prove.For the Vertex Cover addition, I would have to think about the application scenario for a bit.