Description
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)
650 students in the “Analysis of Algorithms” class in 2024 Spring take the exams onsite. The university
provided 7 classrooms for exam use, each classroom i can contain Ci (capacity) students. The safety level
of a classroom is defined as αi(Ci − Si), where αi is the known parameter for classroom i, and Si is the
actual number of students placed to take the exams in the classroom. We want to maximize the total
safety level of all the classrooms. Besides, to guarantee good spacing, the number of students in a
classroom should not exceed half of the capacity of each classroom.
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.