Description
1 Study Group
List the names and SIDs of the members in your study group. If you have no collaborators, write “none”.
2 Local Search for Max Cut
Sometimes, local search algorithms can give good approximations to NP-hard problems. In the Max-Cut problem, we have a graph G(V,E) and we want to find a cut (S,T) with as many edges crossing as possible. One local search algorithm is as follows: Start with any cut, and while there is some vertex v ∈ S such that more edges cross (S −v,T +v) (or some v ∈ T such that more edges cross (S + v,T − v)), move v to the other side of the cut. Note that when we move v from S to T, v must have more neighbors in S than T.
- Give an upper bound on the number of iterations this algorithm can run for (i.e. the total number of times we move a vertex).
- Show that when this algorithm terminates, it finds a cut where at least half the edges in the graph cross the cut.
3 Coffee Shops
A rectangular city is divided into a grid of m×n blocks. You would like to set up coffee shops so that for every block in the city, either there is a coffee shop within the block or there is one in a neighboring block. (There are up to 4 neighboring blocks for every block). It costs rij to rent space for a coffee shop in block ij.
Write an integer linear program to determine which blocks to set up the coffee shops at, so as to minimize the total rental costs.
- What are your variables, and what do they mean?
- What is the objective function?
- What are the constraints?
- Solving the linear program gets you a real-valued solution. How would you round the LP solution to obtain an integer solution to the problem? Describe the algorithm in at most two sentences.
- What is the approximation ratio obtained by your algorithm?
- Briefly justify the approximation ratio.
4 Mechanical Project Problem
In this problem, you will look at a few mechanical examples of the project problem, to build intuition. Consider the graph G = (V,E) below.
Your answers to the following do not require any justification.
- What is the shortest path from s to t in G and what is its length?
- Which edge should be removed to maximize the length of the shortest path if you are allowed to remove k = 1 edge? What is the new shortest path length from s to t?
- Which edges should be removed to maximize the length of the shortest path if you are allowed to remove k = 2 edges? What is the new shortest path length from s to t?
- Suppose that instead of being allowed to remove individual edges, you are allowed to remove exactly one node (not s or t) from the graph. Which node should be removed to maximize the length of the shortest path? What is the new shortest path length from s to t?
