CSPP 55005 Algorithms — Winter 2013

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 TX × Y × Z of ordered triples, a subset M of T is a 3-dimensional matching if each element of XYZ 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.

  5. Given an undirected graph G = (V, E) and an integer k, we want to partition the vertices of G into k subsets S1, S2, …, Sk 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.

Gerry Brady and Janos Simon
Thursday March 7 18:27:06 CST 2013