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)
^ (x1 ∨
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 vi (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).