Description
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:
Similarly the profit ($) contribution per unit varies from plant to plant as below:
2
