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.
------
SAT:
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?