单选题：There are $$n$$ jobs, and each job $$j$$ has a processing time $
There are $$n$$ jobs, and each job $$j$$ has a processing time $$t_j$$. We will use a local search algorithm to partition the jobs into two groups A and B, where set A is assigned to machine $$M_1$$ and set B to $$M_2$$. The time needed to process all of the jobs on the two machines is $$T_1 = \sum_{j\in A} t_j$$, $$T_2 = \sum_{j\in B} t_j$$. The problem is to minimize $$|T_1 - T_2|$$.
Local search: Start by assigning jobs $$1, \ldots, n/2 $$ to $$M_1$$, and the rest to $$M_2$$.
The local moves are to move a single job from one machine to the other, and we only move a job if the move decreases the absolute difference in the processing times. Which of the following statement is true? @[B](3)
A. The problem is NP-hard and the local search algorithm will not terminate.
B. When there are many candidate jobs that can be moved to reduce the absolute difference, if we always move the job $$j$$ with maximum $$t_j$$, then the local search terminates in at most $$n$$ moves.
C. The local search algorithm always returns an optimal solution.
D. The local search algorithm always returns a local solution with $$\frac{1}{2} T_1 \leq T_2 \leq 2 T_1$$.
A.The problem is NP-hard and the local search algorithm will not terminate.
B.When there are many candidate jobs that can be moved to reduce the absolute difference, if we always move the job $$j$$ with maximum $$t_j$$, then the local search terminates in at most $$n$$ moves.
C.The local search algorithm always returns an optimal solution.
D.The local search algorithm always returns a local solution with $$\frac{1}{2} T_1 \leq T_2 \leq 2 T_1$$.
答案：B
Local search: Start by assigning jobs $$1, \ldots, n/2 $$ to $$M_1$$, and the rest to $$M_2$$.
The local moves are to move a single job from one machine to the other, and we only move a job if the move decreases the absolute difference in the processing times. Which of the following statement is true? @[B](3)
A. The problem is NP-hard and the local search algorithm will not terminate.
B. When there are many candidate jobs that can be moved to reduce the absolute difference, if we always move the job $$j$$ with maximum $$t_j$$, then the local search terminates in at most $$n$$ moves.
C. The local search algorithm always returns an optimal solution.
D. The local search algorithm always returns a local solution with $$\frac{1}{2} T_1 \leq T_2 \leq 2 T_1$$.
A.The problem is NP-hard and the local search algorithm will not terminate.
B.When there are many candidate jobs that can be moved to reduce the absolute difference, if we always move the job $$j$$ with maximum $$t_j$$, then the local search terminates in at most $$n$$ moves.
C.The local search algorithm always returns an optimal solution.
D.The local search algorithm always returns a local solution with $$\frac{1}{2} T_1 \leq T_2 \leq 2 T_1$$.
答案：B