SCS Undergraduate Thesis Topics

2010-2011
Kevin Lewi Anupam Gupta Online Metric Matching on the Line
     

Given a metric space, a set of points with distances satisfying the triangle inequality, a sequence of requests arrive in an online manner. Each request must be irrevocably assigned to a unique server before future requests are seen. The goal is to minimize the sum of the distances between the requests and the servers to which they are matched. We study this problem under the framework of competitive analysis.

We give two O(log k)-competitive randomized algorithms, where k is the number of servers. These improve on the best previously known O(log2 k)-competitive algorithm for this problem. Our technique is to embed the line into a distribution of trees in a distance-preserving fashion, and give algorithms that solve the problem on these trees. Our results are focused on settings for the line, but these results can also be extended to all constant-dimensional metric spaces.


Close this window