[SOLVED] Csci570 – homework 12

Q1)
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: Given an undirected graph G(V, E), where V has an even number of vertices, find an equal partition of V into two sets A and B, maximizing the size of E(A,B).
Provide a factor 2-approximation algorithm for solving the Max Equal Cut problem and prove the approximation ratio for the algorithm. (15 points)
Hint: Iteratively build A and B. At each step consider a pair of vertices, and put one in each of A and B to ensure they are equal. Decide which of the two vertices goes to which side to greedily maximize E(A, B) in that step.
Q2)
Express the problem as a integer linear programming problem to obtain the number of students to be placed in each room. You DO NOT need to numerically solve the program. (15 points)
a) Define your variables.
b) Write down the objective function.
c) Write the constraints.
Q3)
Write down the problem of finding a Min-s-t-Cut of a directed network with source s and sink t as problem as an Integer Linear Program. (20 pts)
a) Define your variables.
b) Write down the objective function.
c) Write the constraints.
Ungraded problems
Q4)
Suppose you have a knapsack with maximum weight W and maximum volume V . We have n dividable objects. Each object i has value mi, weights wi and takes vi volume. Now we want to maximize the total value in this knapsack, and at the same time We want to use up all the space (volume) in the knapsack. Formulate this problem as a linear programming problem. You DO NOT have to solve the resulting LP.
Q5)
A Max-Cut of an undirected graph G = (V,E) is defined as a cut Cmax such that the number of edges crossing Cmax is the maximum possible among all cuts. Consider the following algorithm.
i) Start with an arbitrary cut C.
ii) While there exists a vertex v such that moving v from one side of C to the other increases the number of edges crossing C, move v and update C.
Prove that the algorithm is a 2-approximation, that is the number of edges crossing Cmax is at most twice the number crossing C.