Homework 8 (assigned March 7, due March 13)

Reading: CLRS chapter 35.

Written assignment: Solve the following "Do" exercises and assigned problems. Only solutions to the assigned problems should be turned in.

"Do" Exercises (not to be handed in):

1. Exercise 35.4-1, page 1127.

2. Exercise 35.4-2, page 1127.

3. Exercise 35.4-4, page 1128.

4. Problem 35-2, pages 1134–1135.

Problems (to be handed in):

1. Problem 35-1, page 1134. (25 points: parts a–e, 4 points each; part f, 5 points).

2. Problem 35-5, pages 1136–1137. (15 points: parts a, b, 2 points each; part c, 6 points; part d, 5 points.)

3. Problem 35-7, pages 1137–1138. (25 points: 5 points for each part)

4. Given disjoint sets X, Y, and Z, and given a set T ⊆ X × Y × Z of ordered triples, a subset M of T is a 3-dimensional matching if each element of X ∪ Y ∪ Z is contained in at most one of these triples. The maximal 3-dimensional matching problem is to find a 3-dimensional matching M of maximum size. The size of the matching is the number of triples it contains. Assume |X| = |Y| = |Z|. Give an efficient approximation algorithm that finds a 3-dimensional matching of size at least 1/3 times the maximum possible size, i.e., the optimal 3-dimensional matching can have at most 3 times as many edges as the set returned by your algorithm.
   • Describe your algorithm in pseudocode. (6 points)
   • Analyze the running time of your algorithm. (1 point)
   • Argue that your algorithm always produces a 1/3-approximation. (3 points)

5. Given an undirected graph G = (V, E) and an integer k, we want to partition the vertices of G into k subsets S₁, S₂, …, S_k in order to maximize the number of edges that have endpoints in different subsets. Give an efficient (1 − 1/k)-factor approximation algorithm for this problem.
   • Describe your algorithm in pseudocode. (6 points)
   • Analyze the running time of your algorithm. (1 point)
   • Argue that your algorithm always produces a (1 − 1/k) approximation. (3 points)