In class we saw an instance of a set cover problem in which the greedy heuristic (at each step choose the set that covers the most uncovered elements) achieves an approximation ratio of 4/3.
Find an instance with three sets in which the greedy heuristic necessarily achieves an approximation ratio of 3/2.
Find another instance where the approximation ratio is larger than 3/2.
In the (NP-complete) maximum independent set problem, we must find a subset of the vertices of a graph that is as large as possible, with no two vertices in the subset adjacent to each other. Formulate this as a {0,1} integer programming problem and describe the corresponding linear programming relaxation, such that the value of the linear program is always greater than or equal to the size of the maximum independent set. What is the value of your linear program on a graph with n vertices, all pairs of which are adjacent?
What is the value of the semidefinite programming relaxation of the maximum cut problem on the complete tripartite graph K2,2,2 (the graph of the regular octahedron)?
Consider the following randomized heuristic for the weighted maximum cut problem: simply assign each vertex to one of the two subsets of vertices randomly, with probability 1/2 for each subset, independently from all the other vertices.
What is the expected approximation ratio of this algorithm?
Apply the method of conditional probabilities to this method, giving a deterministic approximation algorithm with the same approximation ratio, and describe the resulting deterministic algorithm.