General Information

 Student: Igor Balla Email: iballa@cmu.edu Office: CoRE 442 School: Carnegie Mellon University Faculty Advisor: Howard Karloff, AT&T Labs Project: Randomized, Approximation and Online Algorithms

Project Description

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 [2] 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)

K-Server Problem
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 [3] give an algorithm and show it is 2k-1 competitive). However, not many results using randomized algorithms are known. Chrobak, Karloff, Payne, and Vishwanathan [1] 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.

Project Log

Week 1: Met with my mentor the week before. He gave me the paper on approximating metrics by a distribution on tree metrics [2], 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 [2]. 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 [1] for the (k,l) problem on the line?

Week 6: 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.

Week 8: 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.

Rutgers DIMACS

[1] Marek Chrobak, Howard Karloff, Tom H. Payne, and Sundar Vishwanathan. New results on server problems. SIAM J. Discrete Math., 4:172-181, 1991.

[2] 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.

[3] Elias Koutsoupias and Christos Papadimitriou. On the k-server conjecture. J. ACM, 42:971-983, 1995.