HW 12

        1. [20 points] 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 a 12 approximation al-gorithm that you can find for the problem.



        2. [20 points] Write down the problem of finding a Min-s-t-Cut of a di-rected network with source s and sink t as an Integer Linear Program and explain your program.

        3. [10 points] 720 students have pre-enrolled for the “Analysis of Al-gorithms” class in Fall. Each student must attend one of the 16 discussion sections, and each discussion section i has capacity for Di students. The hap-piness 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. [16 points] 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

1





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 num-ber of constraints needed and describe what each constraint represents (8 pts).




        5. (Ungraded) Given a graph G and two vertex sets A and B, let E(A, B) denote the set of edges with one endpoint in A and one endpoint in B. The Max Equal Cut problem is defined as follows

Instance Graph G(V, E), V = 1, 2, ..., 2n.

Question Find a partition of V into two n-vertex sets A and B, maximizing the size of E(A, B).

Provide a factor 12 -approximation algorithm for solving the Max Equal Cut problem.











2