Raghvendra, Sharath
A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching
Abstract
We study the Online Minimum Metric Bipartite Matching Problem. In this problem, we are given point sets S and R which correspond to the server and request locations; here S=R=n. All these locations are points from some metric space and the cost of matching a server to a request is given by the distance between their locations in this space. In this problem, the request points arrive one at a time. When a request arrives, we must immediately and irrevocably match it to a "free" server. The matching obtained after all the requests are processed is the online matching M. The cost of M is the sum of the cost of its edges. The performance of any online algorithm is the worstcase ratio of the cost of its online solution M to the minimumcost matching.
We present a deterministic online algorithm for this problem. Our algorithm is the first to simultaneously achieve optimal performances in the wellknown adversarial and the random arrival models. For the adversarial model, we obtain a competitive ratio of 2n1 + o(1); it is known that no deterministic algorithm can do better than 2n1. In the random arrival model, our algorithm obtains a competitive ratio of 2H_n  1 + o(1); where H_n is the nth Harmonic number. We also prove that any online algorithm will have a competitive ratio of at least 2H_n  1o(1) in this model.
We use a new variation of the offline primaldual method for computing minimum cost matching to compute the online matching. Our primaldual method is based on a relaxed linearprogram. Under metric costs, this specific relaxation helps us relate the cost of the online matching with the offline matching leading to its robust properties.
BibTeX  Entry
@InProceedings{raghvendra:LIPIcs:2016:6641,
author = {Sharath Raghvendra},
title = {{A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
pages = {18:118:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770187},
ISSN = {18688969},
year = {2016},
volume = {60},
editor = {Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6641},
URN = {urn:nbn:de:0030drops66410},
doi = {10.4230/LIPIcs.APPROXRANDOM.2016.18},
annote = {Keywords: Online Algorithms, Metric Bipartite Matching}
}
06.09.2016
Keywords: 

Online Algorithms, Metric Bipartite Matching 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Issue date: 

2016 
Date of publication: 

06.09.2016 