Analysis of Algorithms : An Active Learning Approach

8.2 TYPICAL NP PROBLEMS 223

number of terms, the possible combination of trues and falses that would have

to be checked can get very large.

■ 8.2.6 Job Scheduling Problem

We have a set of jobs with the amount of time they need to complete, t 1 ,t 2 ,... ,

tN, the deadline they need to be completed by, d 1 ,d 2 ,... , dN, and a penalty

incurred if the job is not completed by the deadline, p 1 ,p 2 ,... , pN. The optimi-

zation problem attempts to order the jobs so as to incur the smallest penalty. The

decision problem asks if there is a schedule that has a penalty less than P.

8.2.7

1. In Section 8.1, a two-step nondeterministic process was described for solv-
   ing problems in the class NP. Give the process that could be used for the fol-
   lowing problems. Your answer should describe the format of the output of
   the nondeterministic step. This output should have all of the elements that
   are part of the solution to the whole problem. For example, for the traveling
   salesperson problem, this was a list of cities in the order of the visits. Then
   your answer should describe a process that would be used to check to see if
   this generated “solution” satisfies the problem.
   a. Graph coloring problem
   b. Bin packing problem
   c. Backpack problem
   d. Subset sum problem
   e. CNF-satisfiability problem
   f. Job scheduling problem


2. In Section 8.1, a process to transform one problem into another was dis-
   cussed as a way to identify problems that are NP-complete. All of the prob-
   lems in Section 8.1 and 8.2 are NP-complete, so any of these problems can
   be transformed into any other problem. For the following sets of problems,
   describe how you would transform the first into the second:
   a. Backpack problem, bin packing
   b. Bin packing, job scheduling
   c. Job scheduling, subset sum
   d. Subset sum, traveling salesperson
   e. Traveling salesperson, job scheduling

■8.2.7 EXERCISES