Maximum Matching in the Online Batch-arrival Model

Euiwoong Lee, Sahil Singla

Research output: Contribution to journalArticlepeer-review

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, i.e., it 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 ratio 12 + 2-O(s). Our algorithms use a novel Instance-Optimal-LP and combine graph decomposition techniques with online primal-dual analysis.

Original languageEnglish (US)
Article number3399676
JournalACM Transactions on Algorithms
Volume16
Issue number4
DOIs
StatePublished - Sep 2020

All Science Journal Classification (ASJC) codes

  • Mathematics (miscellaneous)

Keywords

  • competitive ratio
  • Edmonds-Gallai decomposition
  • matching
  • OnlineAlgorithms
  • 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