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.
