License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.18
URN: urn:nbn:de:0030-drops-66410
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6641/
Go to the corresponding LIPIcs Volume Portal

Raghvendra, Sharath

A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching

pdf-format:
LIPIcs-APPROX-RANDOM-2016-18.pdf (0.5 MB)

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 worst-case ratio of the cost of its online solution M to the minimum-cost matching.

We present a deterministic online algorithm for this problem. Our algorithm is the first to simultaneously achieve optimal performances in the well-known adversarial and the random arrival models. For the adversarial model, we obtain a competitive ratio of 2n-1 + o(1); it is known that no deterministic algorithm can do better than 2n-1. In the random arrival model, our algorithm obtains a competitive ratio of 2H_n - 1 + o(1); where H_n is the n-th Harmonic number. We also prove that any online algorithm will have a competitive ratio of at least 2H_n - 1-o(1) in this model.

We use a new variation of the offline primal-dual method for computing minimum cost matching to compute the online matching. Our primal-dual method is based on a relaxed linear-program. 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:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6641},
  URN =		{urn:nbn:de:0030-drops-66410},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.18},
  annote =	{Keywords: Online Algorithms, Metric Bipartite Matching}
}

Keywords: Online Algorithms, Metric Bipartite Matching
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Issue Date: 2016
Date of publication: 06.09.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI