Answered

Consider the following instance of the Load Balancing problem: There are m machines and n=2m+1 jobs: 3 jobs are of length m , and 2 jobs are of length m+i for each 1≤i≤m−1. Show that on this instance the list-scheduling algorithm with the LPT rule achieves the approximation ratio 34 − 3m1
​

Answer :

tutorconsortium115

There is an even better approximation algorithm, a so-called PTAS1.

What is the algorithm with the LPT rule?

we are given m machines, and 2m+ 1 jobs. There are three jobs with processing time m, and

2 jobs with processing times m + 1, m + 2, . . . , 2m − 1 each. In case of LPT, all but one of the machines

get two jobs with a total processing time of 3m − 1, and a single machine gets three jobs with a total

of 4m − 1 processing time. Thus, the makespan is 4m − 1. OPT schedules the three m jobs on a single

machine, and the remaining jobs on the remaining m−1 machines, such that each of those machines get

with the exception of one machine receiving three jobs with a total processing time of 4m 1.

the approximation ratio approaches 4/3.

There is an even better approximation algorithm, a so-called PTAS1

for this problem, but it is not

covered by this lecture.

To learn more about algorithm refer to:

https://brainly.com/question/24953880

#SPJ4

Other Questions