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.ITCS.2019.50
URN: urn:nbn:de:0030-drops-101436
URL: https://drops.dagstuhl.de/opus/volltexte/2018/10143/
Go to the corresponding LIPIcs Volume Portal

Kumar, Ravi ; Purohit, Manish ; Schild, Aaron ; Svitkina, Zoya ; Vee, Erik

Semi-Online Bipartite Matching

pdf-format:
LIPIcs-ITCS-2019-50.pdf (0.5 MB)

Abstract

In this paper we introduce the semi-online model that generalizes the classical online computational model. The semi-online model postulates that the unknown future has a predictable part and an adversarial part; these parts can be arbitrarily interleaved. An algorithm in this model operates as in the standard online model, i.e., makes an irrevocable decision at each step.
We consider bipartite matching in the semi-online model. Our main contributions are competitive algorithms for this problem and a near-matching hardness bound. The competitive ratio of the algorithms nicely interpolates between the truly offline setting (i.e., no adversarial part) and the truly online setting (i.e., no predictable part).

BibTeX - Entry

@InProceedings{kumar_et_al:LIPIcs:2018:10143,
  author =	{Ravi Kumar and Manish Purohit and Aaron Schild and Zoya Svitkina and Erik Vee},
  title =	{{Semi-Online Bipartite Matching}},
  booktitle =	{10th Innovations in Theoretical Computer Science  Conference (ITCS 2019)},
  pages =	{50:1--50:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{124},
  editor =	{Avrim Blum},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10143},
  URN =		{urn:nbn:de:0030-drops-101436},
  doi =		{10.4230/LIPIcs.ITCS.2019.50},
  annote =	{Keywords: Semi-Online Algorithms, Bipartite Matching}
}

Keywords: Semi-Online Algorithms, Bipartite Matching
Collection: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Issue Date: 2018
Date of publication: 08.01.2019

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