CSCI 570 - HW 12

CSCI 570 - HW 12

1. 20pts
A variation of the satisfiability problem is the MIN 2-SAT problem. The
goal in the MIN 2-SAT problem is to find a truth assignment that minimizes
the number of satisfied clauses. Give the best approximation algorithm that
you can find for the problem.
2. 15pts
Consider the following vertex cover algorithm for an undirected graph
G = (V, E).
0. Initialize C=Null set.
1. Pick any edge e = (u, v) ∈ E, add u and v to C. Delete all edges incident
on either u or v.
2. If E is empty, output C and exit. Otherwise, go to step 1.
Show that C is a vertex cover and that the size of C is at most twice as big
as the minimum vertex cover. (Thus we have a 2-approximation).
3. 10pts
720 students have pre-enrolled for the “Analysis of Algorithms” class in
Fall. Each student must attend one of the 16 discussion sections, and each
discussion section i has capacity for Di students. The happiness level of
a student assigned to a discussion section i is proportionaate to αi(Di −
Si), where αi
is a parameter reflecting how well the air-conditioning sysem
works for the room used for section i (the higher the better), and Si
is the
actual number of students assigned to that section. We want to find out how
many students to assign to each section in order to maximize total student
happiness.
1
Express the problem as a linear programming problem.
4. 16pts
A set of n space stations need your help in building a radar system to track
spaceships traveling between them. The i
th space station is located in 3D
space at coordinates (xi
, yi
, zi). The space stations never move. Each space
station i will have a radar with power ri
, where ri
is to be determined. You
want to figure how powerful to make each space station’s radar transmitter,
so that whenever any spaceship travels in a straight line from one station
to another, it will always be in radar range of either the first space station
(its origin) or the second space station (its destination). A radar with power
r is capable of tracking space ships anywhere in the sphere with radius r
centered at itself. Thus, a space ship is within radar range through its strip
from space station i to space station j if every point along the line from
(xi
, yi
, zi) to (xj
, yj
, zj ) falls within either the sphere of radius ri centered at
(xi
, yi
, zi) or the sphere of radius rj centered at (xj
, yj
, zj ). The cost of each
radar transmitter is proportional to its power, and you want to minimize
the total cost of all of the radar transmitters. You are given all of the
(x1, y1, z1), ...,(xn, yn, zn) values, and your job is to choose values for r1, ..., rn.
Express this problem as a linear program.
(a) Describe your variables for the linear program (3 pts).
(b) Write out the objective function (5 pts).
(c) Describe the set of constraints for LP. You need to specify the number
of constraints needed and describe what each constraint represents (8 pts).
2