2.[25 pts] Formulate the problem of finding a Min-S-T- cut of a directed network with source s and sink t as an Integer Linear Program and explain your program.
3. [25 pts] 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 out how powerful to make each space station’s radar transmitter is, so that whenever any spaceship travels in a straight line from one station to another, it will always be in the 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 spaceship 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 (5 pts).
(b) Write out the objective function (8 pts).
(c) Describe the set of constraints for LP. You need to specify the number of constraints needed and describe what each constraint represents (12 pts)
4. [25 pts] Recall the maximum-bipartite-matching problem. Write a linear program that solves set on the right is R, i.e., 𝐿 ∪ 𝑅 = 𝑉𝐺. = (𝑉, 𝐸)
this problem given a bipartite graph , where the set of vertices on the left is L, and the
