Problem 1
800 students in the “Analysis of Algorithms” class in 2021 Fall take the exams onsite. The university provided 9 classrooms for exam use, each classroom can contain Ci (capacity) students. The safety level of a classroom is proportional to αi(Ci − Si), where αi is the area size of the classroom and Si is the actual number of students taking the exams in the classroom. Due to the pandemic, we want to maximize the safety level of all the classroom. Besides, to guarantee students have a comfort environment, the number of students in a classroom should not exceed half of the capacity of each classroom.
Express the problem as a linear programming problem. You DO NOT need to solve it.
Problem 2
A triangle is a set of three vertices, every two of which is connected by an edge. Consider the following minimization problem that we refer to as triangle removal. The input is a graph G(V, E). The goal is to select a minimum subset of edges whose removal from the graph gives a new graph with no triangles.
Design a strongly polynomial time algorithm that provides a factor 3 ap-proximation for triangle removal.
Problem 3
A company makes three products and has 4 available manufacturing plants. The production time (in minutes) per unit produced varies from plant to plant as shown below:
Product
Manufacturing Plant
1
2
3
4
1
5
7
4
10
2
6
12
8
15
3
13
14
9
17
1
Similarly the profit ($) contribution per unit varies from plant to plant as below:
Product
Manufacturing Plant
1
2
3
4
1
10
8
6
9
2
18
20
15
17
3
15
16
13
17
If, one week, there are 35 working hours available at each manufacturing plant how much of each product should be produced given that we need at least 100 units of product 1, 150 units of product 2 and 100 units of product
3. Formulate this problem as a linear program. You do not have to solve the resulting LP.
Ungraded Problems
Problem 1
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 in the knapsack. Formulate this problem as a linear programming problem. You DO NOT have to solve the resulting LP.
Problem 2
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
Instance Graph G(V, E), V = {1, 2, ..., 2n}.
Question Find a partition of V into two n-vertex sets A and B, maximizing the size of E(A, B).
Provide a factor 1/2-approximation algorithm for solving the Max Equal Cut problem.
2
