MS&E 319: Approximation Algorithms for Optimization Problems, Winter 2004-05

Instructor: Ashish Goel

Handout 3: Homeworks 2 and 3, combined.


Given:2/28/2005. Due: 3/10/2005.


You can collaborate with other students in this class to any extent, but under no conditions can you read another studentís answer or ask another person to write yours.


  1. Problem 10.2 from the text: Give an FPTAS for the minimum makespan problem when the number of machines, m, is a fixed constant.
  2. In the class we claimed that for the k-median problem, going via tree embeddings yields an O(log n) randomized approximation algorithm.

a)     To complete the argument given in class, we need to present a polynomial time algorithm to solve the k-median problem when the underlying graph is a tree. Present the algorithm for the simpler case when the underlying graph is a line. Then, read the paper (it is okay to group-read)

Arie Tamir. An O(pn2) algorithm for p-median and related problems on tree graphs. Operations Research Letters, 19:59--64, 1996.

b)    Consider the minimum k-center problem, where we have to choose a set S of k vertices from a metric space (V,d) such that  the quantity

MAXv ő V d(v,S)

is minimized. Does the tree-embedding approach immediately yield an O(log n) approximation for the minimum k-center problem? How or why not?

  1. Present a polynomial time algorithm that results in a 2-approximation for the minimum k-center problem. Prove the bound on the approximation ratio. Hint: Greedy.
  2. Consider the following variant of approximate majorization: Given two m-dimensional vectors x and y of non-negative real numbers, x £a y if Sj(x) £ aSj(y) for all 1 £ j £ m. Here, Sj(x) refers to the j-th suffix sum, i.e., the sum of the j largest components of x.

a)     Let Lj be the total load assigned to machine j by Grahamís rule. Prove that L £2 P for any other feasible vector P of total loads.

b)    (Optional) Prove that x £a y Ř f(x/a) £ f(y) for all m-variate, symmetric, non-decreasing, convex functions f which satisfy f(0) = 0. Give two non-trivial examples of such functions.

  1.  Present a simple example to show that trees cannot be isometrically emdedded into l2. Present another simple example to show that l2 cannot be isometrically embedded into a tree. Prove that l2 cannot be isometrically embedded into a probability distribution over trees if each individual tree in the distribution must be non-contracting.
  2. Consider n uniformly spaced points on a line. What is the distortion obtained when these points are embedded into l1 using Bourgainís algorithm? Suggestion unrelated to this problem: The line metric is an excellent metric to obtain intuition into Bourgainís embeddings. For example, consider pairs (1,n), (1,2), and (n/2, n/2 +1). Which of the log n sets are the most relevant for distinguishing between the two elements in each pair?
  3. Practice problem: 21.31 from the text (do not submit).