CSCI 570 – Fall 2020 – HW 12 Solution
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.
Solution. We assume that no clause contains a variable as well as the complement of the variable. (Such clauses are satisfied regardless of the truth assignment used.)
We give a 2-approximation algorithm as follows: Let I be an instance of MIN SAT consisting of the clause set CI and variable set XI . Construct an auxiliary graph GI (VI , EI ) corresponding to I as follows. The node set VI is in one-to-one correspondence with the clause set CI. For any two nodes vi and vj in VI, the edge (vi,vj) is in EI if and only if the corresponding clauses ci and cj are such that there is a variable x belongs to XI that appears in un-complemented form in ci and complemented form in cj, or vice versa.
To construct a truth assignment, we construct an approximate vertex cover V ′ for GI such that |V ′| is at most twice that of a minimum vertex cover for GI . Then construct a truth assignment that causes all clauses in VI − V ′ to be false. (For a method to find an approximate vertex cover, please refer to section 11.4 in the textbook.)
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).
Solution. Every edge e ∈ E was either picked in step 1 or deleted in step 1. If it was picked, then both its edges were added to C and is hence
1
covered. If it was deleted, then it already had at least one incident vertex contained in C and is hence covered. Thus C is indeed a vertex cover.
Let M be the set of edges picked in step 1. let Copt be an minimal vertex cover. Observe that no two edges in M share a vertex (When we pick an e, the deletion step ensures that no other edge that shares an edge with e is ever picked). Thus for each edge e ∈ M, Copt has to contain at least one of its incident vertex (Moreover these vertex are distinct as reasoned in the previous line). Hence
|Copt| ≥ |M|.
From the algorithm, we have that |C| = 2|M|. Thus
|C| ≤ 2|Copt|
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. Solution. Our variables will be Si. Our objective function is:
16
maximize αi(Di − Si) i=1
subjectto Di−Si≥0fori=1,…,16 Si ≥ 0 for i = 1, . . . , 16
16
Si =720 i=1
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). 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
2
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.
Solution. (a) ri = the power of the ith radar transmitter, i = 1, . . . , n.
(b) Minimize r1 +r2 +···+rn.
(c) ri +rj ≥(xi −xj)2 +(yi −yj)2 +(zi −zj)2.
Or equivalently, ri + rj ≥ di,j for each pair of stations i and j, where di,j is the distance from station i to station j.
We need (n2 − n)/2 constraints of inequality.
3