Load balancing problem - 2 approximation algorithm, greedy algorithm
Budget: $10 – $30 USD
Let’s take an example. We have 10 machines. The jobs arrive continuously throughout the day, and each job takes between 1 to 25 units of time (that is, a job costing 25 is the largest job that will arrive. Let’s also say that a large number of jobs arrive each day, costing a total of approximately 2500.
In this example we know something about the data. We know that a huge job won’t come in at the end, because the jobs aren’t very large. In the above example, the approximation factor is better than 2 times the optimal. What is it, and why?
In this example we know something about the data. We know that a huge job won’t come in at the end, because the jobs aren’t very large. In the above example, the approximation factor is better than 2 times the optimal. What is it, and why?