Algorithm Design Techniques

 COMP-360              Assignment 4              Due: 5pm Thursday December 1, 2005

Please leave your assignment in the box marked COMP360, 1st floor McConnell.
Late assignments  -10% per day, including weekends.
Hand in late assignments to the T.A.

1. A supermarket keeps records of everything each customer buys. They want to find the largest subset of their customers such that no two of them have ever bought the same item. Show this problem is NP-hard.

2. A summer camp is hiring counselors. There are n activities at the camp, and each job applicant submits a list of those activities that she can supervise. The camp wants to hire the minimum number of counselors such that each activity has at least one superviser. Show this problem is NP-hard.

3. (a) You have set of n jobs with running times t1 , t2 , ... , tn. You are required to schedule these jobs as efficiently as possible onto m machines, so that all jobs are finished by some time T, and T is as small as possible. Formulate an exact solution to this problem as an integer linear program.

(b) Let m=5, n=11, with job times 95,93,82,81,78,77,66,64,53,52,51. Schedule these using the list decreasing heuristic and compare the result with that obtained by solving the integer program by lp_solve.

4. Show directly that SAT is polynomially reducible to VERTEX COVER. Ie. each input to the satisfiability problem SAT should be mapped to an input for VERTEX COVER, so that the answers are the same.
Input: 2n literals, which are boolean variables x1 , x2 , ... , xn and their complements. A set of clauses C1,...,Cm each of which contains one or more literals.
Question: Can the variables be given values true or false so that in each clause at least one literal is true?