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.ESA.2017.22
URN: urn:nbn:de:0030-drops-78206
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7820/
Go to the corresponding LIPIcs Volume Portal

Buchbinder, Niv ; Segev, Danny ; Tkach, Yevgeny

Online Algorithms for Maximum Cardinality Matching with Edge Arrivals

pdf-format:
LIPIcs-ESA-2017-22.pdf (0.5 MB)

Abstract

In the adversarial edge arrival model for maximum cardinality matching, edges of an unknown graph are revealed one-by-one in arbitrary order, and should be irrevocably accepted or rejected. Here, the goal of an online algorithm is to maximize the number of accepted edges while maintaining a feasible matching at any point in time. For this model, the standard greedy heuristic is 1/2-competitive, and on the other hand, no algorithm that outperforms this ratio is currently known, even for very simple graphs.

We present a clean Min-Index framework for devising a family of randomized algorithms, and provide a number of positive and negative results in this context. Among these results, we present a 5/9-competitive algorithm when the underlying graph is a forest, and prove that this ratio is best possible within the Min-Index framework. In addition, we prove a new general upper bound of 2/(3+1/phi^2) ~ 0.5914 on the competitiveness of any algorithm in the edge arrival model. Interestingly, this bound holds even for an easier model in which vertices (along with their adjacent edges) arrive online, and when the underlying graph is a tree of maximum degree at most 3.

BibTeX - Entry

@InProceedings{buchbinder_et_al:LIPIcs:2017:7820,
  author =	{Niv Buchbinder and Danny Segev and Yevgeny Tkach},
  title =	{{Online Algorithms for Maximum Cardinality Matching with Edge Arrivals}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{22:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Kirk Pruhs and Christian Sohler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7820},
  URN =		{urn:nbn:de:0030-drops-78206},
  doi =		{10.4230/LIPIcs.ESA.2017.22},
  annote =	{Keywords: Maximum matching, online algorithms, competitive analysis, primal-dual method}
}

Keywords: Maximum matching, online algorithms, competitive analysis, primal-dual method
Collection: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 01.09.2017

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