CSCI 570 – Fall 2020 – HW 12
Due November 30st 11:59pm 2020
1. 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 mini- mizes the number of satisfied clauses. Give the best approximation algo- rithm that you can find for the problem.
2. Consider the following vertex cover algorithm for an undirected graph G = (V,E).
(1) Initialize C = ∅. (2)Pickanyedgee=(u,v)∈E,adduandvtoC. Deletealledges
incident on either u or v.
(3) If E is empty, output C and exit. Otherwise, go to step 2.
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. 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.
Express the problem as a linear programming problem.
4. A set of n space stations need your help in building a radar system to track spaceships traveling between them. The ith 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).
1
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. (b) Write out the objective function.
(c) Describe the set of constraints for LP. You need to specify the number of constraints needed and describe what each constraint represents.
2