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(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?
- 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 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.
- 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.
- 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?
- Practice problem:
21.31 from the text (do not submit).