Given: $n$ tasks with accomplishment times $t_1, t_2, \ldots , t_n$. There is no such task that its accomplishment time is greater than the overall accomplishment time of other tasks.

Question: How to distribute these tasks between two workers in a such way that $|T_1 - T_2|$ is minimum ($T_i$ - the overall accompl. time for the $i$-th worker accordingly).

We will use the local search algorithm, starting with a random distribution and redistributing one task on every step only if it leads to reducing $|T_1 - T_2|$ as long as it's possible.

Does this algorithm find the optimal distribution or is there any counterexample?


1 Answer 1


We can consider the more general problem of makespan, in which we wish to partition the tasks into $m$ sets as evenly as possible (your case is $m=2$). We measure the quality of our solution using the maximum total sum of a set, which we wish to minimize. Finn and Horowitz showed that the locality gap for this problem is $2-2/(m+1)$. This means that a locally optimal solution has objective value larger by a factor of at most $2-2/(m+1)$, and moreover there are examples in which the ratio approaches $2-2/(m+1)$. In particular, local search doesn't always give the optimal solution.

For other local search algorithms for makespan, consult the survey of Schuurman and Vredeveld.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.