CSCI 570  Homework 12

CSCI 570 
Homework 12
Graded Problems
1. Consider the following heuristic to compute a vertex cover of a connected graph G. Pick an arbitrary vertex as the root
and perform depth first search. Output the set of non-leaf vertices (vertices of degree greater than 1) in the resulting depth
first search tree.
(a) Show that the output is a vertex cover for G. (10pts)
(b) How good of an approximation to a minimum vertex cover does this heuristic assure? That is, upper bound the ratio
of the number of vertices in the output to the number of vertices in a minimum vertex cover of G.(15pts)
2. 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.
a Does the algorithm terminate in time polynomial in |V |?
b Prove that the algorithm is a 2-approximation, that is the number of edges crossing Cmax is at most twice the number
crossing C.
3. 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. (15pts)
4. 750 students in the “Analysis of Algorithms” class in 2022 Spring 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 total 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.
1 of 2 Professor: Dr. Shahriar Shamsian
CSCI 570 Spring 2022 Due: 04/27/2022
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 of 2 Professor: Dr. Shahriar Shamsian