Reference no: EM131291317
Complete Problem 5 on pages 651 - 659 in Algorithm Design by Kleinberg and Tardos.
You are asked to consult for a business where clients bring in jobs each day for processing. Each job has a processing time ti 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 so¬lutions 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 Σiti.
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 < ti < 50 for all jobs i; and the total load Σiti 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.
Problem: 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.
Refer to book Algorithm Design by Kleinberg and Tardos