单选题：** Load balancing problem: **

** Load balancing problem: **
We have $$n$$ jobs $$j=1, 2, \ldots, n$$ each with processing time $$p_j$$ being an integer number.
Our task is to find a schedule assigning $$n$$ jobs to $$100$$ identical machines so as to minimize the makespan (the maximum completion time over all the machines).

We adopt the following local search to solve the above load balancing problem.

**LocalSearch: **

Start with an arbitrary schedule.

Repeat the following until no job can be re-assigned:

* Let $$l $$ be a job that finishes last.
* If there exists a machine $$i$$ such that assigning job $$l$$ to $$i$$ allows $$l$$ finish earlier, then re-assign $$l$$ to be the last job on machine $$i$$.
* If such a machine is not unique, always select the one with the minimum completion time.

We claim the following four statements:
1. The algorithm LocalSearch finishes within polynomial time.
2. The Load-balancing problem is NP-hard.
3. Let OPT be the makespan of an optimal algorithm. Then the algorithm LocalSearch finds a schedule with the makespan at most of 1.95 OPT.
4. This algorithm finishes within $$O(n^2)$$.

How many statments are correct ?
@[D](3)

A. 0
B. 1
C. 2
D. 3
E. 4



A.0
B.1
C.2
D.3
E.4


答案：D