Algorithm Design Techniques

 COMP-360              Assignment 5      Due: Monday,  Nov 30, 5pm

No late assignments!

If you work closely with someone else, indicate the person's name(s) on your homework.
The final write-up of each assignment must, however, be your own work.

Except for Problem 1, you may assume that SAT, 3-SAT, IND SET, VERTEX COVER, SET COVER and SUBSET SUM are known to be NP-complete.

1.  VERTEX COVER: Input: Graph G=(V,E), integer k.
Question: Is there a subset S of V with |S|=k such that every edge in E has at least one endpoint in S?

(a) Show this problem is NP.
(b) Give a direct reduction from SAT(Text, P. 460)  to VERTEX COVER, and prove its correctness.
(c) Illustrate your reduction by constructing the VERTEX COVER input corresponding to the SAT input:

                    (x1  ∨ x2 ) ^ (x1  ∨ x2  ∨ x3  ∨ x4) ^ (x x2  ∨ x3) ^(x2  ∨ x3 v x4)           

2.  Text, P. 505 problem 2.

3.  Text, P. 513, problem 15

4.  You are planning to move to Asia and are considering whether to ship some of your stuff. Assume you have n possible items to send.
For each item i, you have a value pi, a weight wi and a volume v(you may assume these are all integers).
For a fixed shipping cost of $C, there is a maximum weight limit of W and a maximum volume limit of V.
Show that it  is NP-complete to decide whether to ship anything or not, by reducing one of the given NP-complete problems to it.
Formulate the problem as an integer program.

5.  (Worth the same as problems 1-4 combined).
Below are three variations of the 3SAT problem, each of which is NP-complete.
In each case you have n input variables x1 ... xn and m clauses with three terms based on three distinct variables in each clause.
(A term is either xi or it's complement xi )

3SAT:          Can you assign truth values to the variables so that each clause has at least one true term?
NAE-3SAT: Can you assign truth values to the variables so that each clause has either one or two true terms?
1-OF-3SAT: Can you assign truth values to the variables so that each clause has exactly one true term?

Do the following for each problem:
(a) Formulate it as an integer program.
(b) Write a program or script to generate 20 random instances in the format for lp_solve.
Each of the clauses should contain three terms based on three distinct variables chosen at random from the 2n terms.
(c) Set n=40 and using lp_solve determine roughly how large m should be so that about half of the randomly generated instances have a "yes" answer.
(d) Now scale up n and m linearly to determine roughly how large an instance of each type can be solved by lp_solve in 1 minute and in 5 minutes of cpu time.

Hand in you program/script for part (b). Give statistics on the outcomes of your experiments to justify your answers to (c) and (d).