Problem 2 (10 points) Here is another task scheduling problem. We are given n tasks, where the duration of task i is di, D = d1 + + dn. Two teams, A;B, are available to work on these tasks, and we can distribute tasks arbitrarily between them. Each team can only perform the tasks it gets, consecutively. The question is how to distribute the tasks between the two teams so that all tasks are nished by the earliest possible time (so the larger nishing time is as small as possible). This is a hard problem, so your question is only this: nd a greedy algorithm, and estimate (with proof) how much worse it can be than the optimum: say, by a factor 2, 1.5, 3? [Hint: Compare to the ideal (not necessarily achievable) result D=2.]

Problem 2 (10 points) Here is another task scheduling problem. We are given n tasks, where the duration of task i is di, D = d1 +...+ dn. Two teams, A, B, are available to work on these tasks, and we can distribute tasks arbitrarily between them. Each team can only perform the tasks it gets, consecutively. The question is how to distribute the tasks between the two teams so that all tasks are finished by the earliest possible time (so the larger finishing time is as small as possible). This is a hard problem, so your question is only this: find a greedy algorithm, and estimate (with proof) how much worse it can be than the optimum: say, by a factor 2, 1.5, 3? (Hint: Compare to the ideal (not necessarily achievable) result D2. Problem 2 (10 points) Here is another task scheduling problem. We are given n tasks, where the duration of task i is di, D = d1 +...+ dn. Two teams, A, B, are available to work on these tasks, and we can distribute tasks arbitrarily between them. Each team can only perform the tasks it gets, consecutively. The question is how to distribute the tasks between the two teams so that all tasks are finished by the earliest possible time (so the larger finishing time is as small as possible). This is a hard problem, so your question is only this: find a greedy algorithm, and estimate (with proof) how much worse it can be than the optimum: say, by a factor 2, 1.5, 3? (Hint: Compare to the ideal (not necessarily achievable) result D2