Analysis of Deterministic Algorithms for Online Metric Matching

Online Metric Matching is an online problem in which there are k servers and n requests placed on a metric space. The positions of the requests are revealed one by one and an online algorithm has to irrevocably match one request to an available server as soon as it's revealed. The goal of the algorithm is to minimize the total cost of the matching it makes, where the cost of a single match is the distance between the request and the server. An online algorithm is evaluated by computing the ratio of the total cost of its matching over to the total cost of the ideal optimal offline solution. Such ratio is called competitive ratio and an online algorithm is defined as c-competitive if it can achieve a competitive ratio of c. This thesis provides a re-parametrized analysis of the two most studied online algorithms for Online Metric Matching: Nearest Neighbor and Permutation. We provide demonstrations for known but never proved results. In particular, we prove that Permutation can't be O(k)-competitive by providing an instance where it is Omega(n)-competitive for k as low as four. Additionally, we show that Nearest Neighbor is (2^k-1)-competitive.