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.SoCG.2018.67
URN: urn:nbn:de:0030-drops-87803
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8780/
Go to the corresponding LIPIcs Volume Portal

Raghvendra, Sharath

Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line

pdf-format:
LIPIcs-SoCG-2018-67.pdf (0.5 MB)

Abstract

In the online metric bipartite matching problem, we are given a set S of server locations in a metric space. Requests arrive one at a time, and on its arrival, we need to immediately and irrevocably match it to a server at a cost which is equal to the distance between these locations. A alpha-competitive algorithm will assign requests to servers so that the total cost is at most alpha times the cost of M_{Opt} where M_{Opt} is the minimum cost matching between S and R.
We consider this problem in the adversarial model for the case where S and R are points on a line and |S|=|R|=n. We improve the analysis of the deterministic Robust Matching Algorithm (RM-Algorithm, Nayyar and Raghvendra FOCS'17) from O(log^2 n) to an optimal Theta(log n). Previously, only a randomized algorithm under a weaker oblivious adversary achieved a competitive ratio of O(log n) (Gupta and Lewi, ICALP'12). The well-known Work Function Algorithm (WFA) has a competitive ratio of O(n) and Omega(log n) for this problem. Therefore, WFA cannot achieve an asymptotically better competitive ratio than the RM-Algorithm.

BibTeX - Entry

@InProceedings{raghvendra:LIPIcs:2018:8780,
  author =	{Sharath Raghvendra},
  title =	{{Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{67:1--67:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Bettina Speckmann and Csaba D. T{\'o}th},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8780},
  URN =		{urn:nbn:de:0030-drops-87803},
  doi =		{10.4230/LIPIcs.SoCG.2018.67},
  annote =	{Keywords: Bipartite Matching, Online Algorithms, Adversarial Model, Line Metric}
}

Keywords: Bipartite Matching, Online Algorithms, Adversarial Model, Line Metric
Collection: 34th International Symposium on Computational Geometry (SoCG 2018)
Issue Date: 2018
Date of publication: 08.06.2018

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