**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.

- Problem 10.2 from the
text: Give an FPTAS for the minimum makespan problem when the number of
machines, m, is a fixed constant.
- 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(pn^{2}) 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

MAX_{v }_{Î}_{ 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?

- 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.* - Consider the following
variant of approximate majorization: Given two m-dimensional vectors x and
y of non-negative real numbers, x £
^{a}y if S_{j}(x) £ aS_{j}(y) for all 1 £ j £ m. Here, S_{j}(x) refers to the j-th suffix sum, i.e., the sum of the j largest components of x.

a)
Let L_{j} 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.

- Present a simple example to show
that trees cannot be isometrically emdedded into l
_{2}. Present another simple example to show that l_{2}cannot be isometrically embedded into a tree. Prove that l_{2}cannot be isometrically embedded into a probability distribution over trees if each individual tree in the distribution must be non-contracting. - Consider n uniformly
spaced points on a line. What is the distortion obtained when these points
are embedded into l
_{1}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?* - Practice problem:
21.31 from the text (do not submit).