Maximum matching in the online batch-arrival model

Euiwoong Lee, Sahil Singla

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

Abstract

Consider a two-stage matching problem, where edges of an input graph are revealed in two stages (batches) and in each stage we have to immediately and irrevocably extend our matching using the edges from that stage. The natural greedy algorithm is half competitive. Even though there is a huge literature on online matching in adversarial vertex arrival model, no positive results were previously known in adversarial edge arrival model. For two-stage bipartite matching problem, we show that the optimal competitive ratio is exactly 2/3 in both the fractional and the randomized-integral models. Furthermore, our algorithm for fractional bipartite matching is instance optimal—achieves the best competitive ratio for any given first stage graph. We also study natural extensions of this problem to general graphs and to s stages, and present randomized-integral algorithms with competitive ratio12 +2−O(s). Our algorithms use a novel LP and combine graph decomposition techniques with online primal-dual analysis.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings
EditorsFriedrich Eisenbrand, Jochen Koenemann
PublisherSpringer Verlag
Pages355-367
Number of pages13
ISBN (Print)9783319592497
DOIs
StatePublished - 2017
Event19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017 - Waterloo, Canada
Duration: Jun 26 2017Jun 28 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10328 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017
Country/TerritoryCanada
CityWaterloo
Period6/26/176/28/17

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • Competitive ratio
  • Edmonds-Gallai decomposition
  • Matching
  • Online algorithms
  • Primal-dual analysis
  • Semi-streaming

Fingerprint

Dive into the research topics of 'Maximum matching in the online batch-arrival model'. Together they form a unique fingerprint.

Cite this