1. (This is a long homework and may appear to be complicated.)


You have n tasks (homeworks, projects, dates, etc.) at the present moment, and you must finish all of them in the next k days. Tasks cannot be preempted. Thankfully, you know the exact time (in seconds, say {t1 ... tn}) that you need to accomplish each task. However, your discipline prohibits you to end a day with unfinished tasks, which means that every task must be finished on the day that it is started. Since you can only work up to B hours per day (B is the time you can work every day -- assume B is a constant), you want to know whether you can finish all the tasks in the next k days. Call this the WORK decision problem.


WORK is NP-complete (easy reduction from the PARTITION problem -- no points for figuring out the reduction).


1. [6 points] Suppose you have a blackbox B that can solve WORK (with n tasks) in time T(n). Design an algorithm that can return the time-table for a given YES-instance of WORK (i.e., k, B and set of times {t1 ... tn}) (time-table specifies which tasks should be done on which day) in time that is T(n)*poly(n). Describe the algorithm, idea behind its correctness, and complexity.


2. [4 points] Now consider the optimization version of WORK, i.e., you want to determine the minimum number of days needed to finish all tasks. Since you have already studied NP-completeness, and you know how to show the equivalence between WORK and the optimization version (can you?), you do not even try to come up with a clever time-table. Suppose OPT denotes the minimum number of days.
    To schedule them, consider the order they were announced/planned and perform that greedily. That is, try to perform a task on the earliest possible day where it can be done, and move it to a different day if it cannot be performed on any of the earlier days.
    As an example, consider tasks with these times: 300, 900, 300, 800,350,80,50 and B is 1000.
Task 300: Schedule it on day 1, day 1 has 700 seconds left.
Task 900: Cannot be performed on day 1, schedule it on day 2, which now has 100 sec left.
Task 300: Schedule it on day 1, day 1 now has 400 sec left.
Task 800: Cannot be performed on day 1 and day 2, so schedule it on day 3, which now has 200 sec left.
Task 350: Schedule it on day 1, day 1 now has 50 sec left.
Task 80: Cannot be performed on day 1, schedule it on day 2, which now has 20 sec left.
Task 50: Schedule it on day 1, which has no more time left.

  (a) [1 points] Prove that there will be at most 1 day on which you will be working for B/2 or fewer hours.
  (b) [3 points] Say APPROX is the number of days you would require to finish all tasks in this manner. Prove that the minimum number of days is at least APPROX/2.
  (c) [not to be submitted] Prove that if you had instead scheduled the tasks in the order of decreasing times, OPT >= APPROX/1.5.


3. [5 points] Prove that if someone was able to design a polynomial-time (1.5-eps)-approximation algorithm for WORK for any 0 < eps <= 0.5, then we will be able to design a polynomial-time algorithm for PARTITION. Describe the algorithm, idea behind its correctness, and complexity.