TY - GEN
T1 - Maximum matching in the online batch-arrival model
AU - Lee, Euiwoong
AU - Singla, Sahil
N1 - Funding Information:
This work was partially supported by Samsung Scholarship and Simons Award for Graduate Students in Theoretical Computer Science. S. Singla?This work was supported by CMU Presidential Fellowship and NSF awards CCF-1319811, CCF-1536002, and CCF-1617790.
Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - 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.
AB - 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.
KW - Competitive ratio
KW - Edmonds-Gallai decomposition
KW - Matching
KW - Online algorithms
KW - Primal-dual analysis
KW - Semi-streaming
UR - http://www.scopus.com/inward/record.url?scp=85020493440&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85020493440&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-59250-3_29
DO - 10.1007/978-3-319-59250-3_29
M3 - Conference contribution
AN - SCOPUS:85020493440
SN - 9783319592497
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 355
EP - 367
BT - Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings
A2 - Eisenbrand, Friedrich
A2 - Koenemann, Jochen
PB - Springer Verlag
T2 - 19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017
Y2 - 26 June 2017 through 28 June 2017
ER -