@article{31d19b74b03e42558e87cf78319f87cc,
title = "Maximum Matching in the Online Batch-arrival Model",
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.",
keywords = "Edmonds-Gallai decomposition, OnlineAlgorithms, competitive ratio, matching, primal-dual analysis, semi-streaming",
author = "Euiwoong Lee and Sahil Singla",
note = "Funding Information: E.L. was partially supported by Samsung Scholarship and Simons Award for Graduate Students in Theoretical Computer Science. S.S.was supported in part by the Schmidt Foundation, CMUPresidential Fellowship, and NSF awards CCF-1319811, CCF-1536002, and CCF-1617790. Funding Information: E.L. was partially supported by Samsung Scholarship and Simons Award for Graduate Students in Theoretical Computer Science. S.S. was supported in part by the Schmidt Foundation, CMU Presidential Fellowship, and NSF awards CCF-1319811, CCF-1536002, and CCF-1617790. Authors{\textquoteright} addresses: E. Lee, New York University, 251 Mercer Street, New York City, NY, 10012, USA; email: euiwoonl@ cs.cmu.edu; S. Singla, Princeton University and Institute for Advanced Study, 194 Nassau Street, Princeton, NJ, 08542, USA; email: singla@cs.princeton.edu. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. {\textcopyright} 2020 Association for Computing Machinery. 1549-6325/2020/07-ART49 $15.00 https://doi.org/10.1145/3399676 Publisher Copyright: {\textcopyright} 2020 ACM.",
year = "2020",
month = sep,
doi = "10.1145/3399676",
language = "English (US)",
volume = "16",
journal = "ACM Transactions on Algorithms",
issn = "1549-6325",
publisher = "Association for Computing Machinery (ACM)",
number = "4",
}