P1) A directed graph G is a tournament if for any pair of vertices u,v there is exactly one directed edge between u and v, either from u to v or from v to u. Given a tournament with 2n vertices prove that it has a subtournament with at least n + 1 vertices which is acyclic.
For example, in the following picture the red vertices show an acyclic sub-tournament of the given tournament.
P2) We want to design an O(1) approximation algorithm for the following clustering problem. Given a set of n points p1,...,pn ∈Rd, and an integer 1 ≤ k ≤ n, find the minimum radius ∆ and a set of balls of radius ∆ centered at k of the given points such that all of the n points lie in these balls. Note that the balls have radius ∆ with respect to the Euclidean distance.
a) (15 points) Assume that we know the optimum radius ∆. Design a polynomial time algorithm that finds at most k balls of radius O(∆ centered at k of the points covering all of the given points.
Hint. Recall the triangle inequality: For any triple points a,b,c ∈ Rd, a − c2 ≤ a − b2 + b − c2.
b) (5 points) Now, assume that we do not know ∆. Instead suppose we know that the optimum ∆ is in the interval [1,R]1. Use part (a) to design an algorithm that runs in time polynomial in n,logR to find the k balls of radius O(∆).
P3) Recall that maximum independent set is NP-complete. Suppose a friend of yours is came up with an efficient algorithm to solve this problem. Unfortunately, their code does not output the independent set. Instead, for any graph G and any integer k, if G has an independent set of size k it will output “yes” and “no” otherwise. Now, given a graph G with n vertices and an integer 1 ≤ k ≤ n, design a polynomial time algorithm (that only runs their code
1In practice you can take 1,R correspond to be the minimum/maximum pairwise of all of the given points
5-1
polynomially many times) and outputs an independent set of size k in G if it exists, and outputs “Impossible” otherwise.
P4) Draw the dynamic programming table of the following instance of the knapsack problem: You are given 6 items with weight 1,2,4,6,7,9 and value 1,3,6,12,18,25 respectively and the size of your knapsack is 13.
P5) Extra Credit: Design an O(logn) approximation algorithm for weighted set cover problem, i.e., given m sets S1,...,Sm ⊆{1,...,n} such that Si has cost ci ≥ 0, choose a minimum cost family of these sets that cover all of the ground elements {1,...,n}.
