General Information • Project Description • Project Log • Links
Approximating Metric Spaces
The question of approximating a complicated metric space by a simpler one without much distortion is
very important for many problems in computer science. In particular, many approximation problems have been solved for the case where the
metric in question is a tree metric. Thus we would like to be able to approximate arbitrary metrics by tree metrics.
Fakcharoenphol, Rao, and Talwar  show that any metric can be approximated by a distribution on tree metrics with expected distortion
O(log n) (This is in fact tight). We are interested in identifying a smaller class of metric spaces, which can be approximated by a
distribution on tree metrics with expected distortion O(1).
Presentation 1 (ppt)
In this problem you are given a metric space M, and k servers positioned somewhere in M. You get a request one at a time, characterized
by a point in M, and you must move at least 1 server to that point in order to serve the request. Your goal is to make the servers serve the
requests while minimizing the total distance traveled by the servers. If you knew the series of requests ahead of time, you could calculate
the optimal strategy. However, since the requests are coming one at a time, the aim is to devise an algorithm that will do no worse then some
constant C times the optimal. In this case the algorithm is called C competitive. It is well known that any deterministic algorithm cannot
be C competitive for C < k, and the k-server conjecture says that there is in fact a deterministic algorithm that is k-competitive
(Koutsoupias and Papadimitriou  give an algorithm and show it is 2k-1 competitive). However, not many results using randomized algorithms
are known. Chrobak, Karloff, Payne, and Vishwanathan  give a deterministic k competitive algorithm for the case where M is the real line,
but it turns out that no randomized algorithm with a better competitive ratio is known for k > 2. We aim to find a randomized algorithm for
the line with competitive ratio less than k.
Week 1: Met with my mentor the week before. He gave me the paper on approximating metrics by a distribution on
tree metrics , and presented the "radio rebroadcast" problem. Read the paper and tried to understand the idea behind the algorithm. Dr. Karloff
wants me to implement the algorithm but this seems trivial and not my cup of tea. Worked on "radio rebroadcast" a little, without much progress.
Week 2: Reread analysis of algorithm from . Now I understand it well. Created a power point presentation on approximating
metrics. Met with Dr. Karloff, and discussed many things. Most importantly - k-server problem - there are many open questions regarding
randomization of this problem.
Week 4: Read many papers on k-server problem, and tried to get less than 2 competitive ratio for 2 servers on the line.
Met with Dr. Karloff and discussed 2 server 3 point problem and marking algorithm. Found papers that already did randomized 2 server 3 point,
as well as 2 servers on the line. Found nice generalization - (k,l) server problem. Does a deterministic solution for (kr,r) server give a
randomized solution for k server with same ratio? Can I alter DOUBLE COVERAGE  for the (k,l) problem on the line?
Finally proved the competitive ratio of 2 for the randomized memoryless algorithm for 2 servers in general metric space (Harder than I thought).
Now I am curious how far the same algorithm and argument can be extended.
The search for a simple less than 2 competitive algorithm for 2 servers on the line is fruitless. On the other hand, it seems reasonable to extend
the 2 server memoryless algorithm to a 3 server memoryless algorithm - must first solve this on trees. Met with Dr. Karloff and discussed approximating
a 4 point metric space with a distribution on tree metrics (finding best ratio for this seems interesting). Also discussed the conjecture that there
exists a k-competitive randomized memoryless alg for the k-server problem - we both believe it to be false - should try to construct a counter example,
or prove that such a metric space must exist. In fact I believe it to be false for 3 servers.
Links and Resources
 Marek Chrobak, Howard Karloff, Tom H. Payne, and Sundar Vishwanathan. New results on server problems. SIAM J. Discrete Math., 4:172-181, 1991.
 Fakcharoenphol, J., Rao, S., Talwar, K. 2004. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69, 3 (Nov. 2004), 485-497.
 Elias Koutsoupias and Christos Papadimitriou. On the k-server conjecture. J. ACM, 42:971-983, 1995.