Description
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 − c�2 ≤
�a − b�2 + �b − c�2.
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, log R 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(log n) 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}.
5-2
