Fetching the paper…
Reading the bibliography…
We study the problem of computing an approximate maximum cardinality matching in the semi-streaming model when edges arrive in a \emph{random} order.
On graph problems in a semi-streaming model
J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, and J. Zhang · 2005
Earlier work this paper cites.
Finding graph matchings in data streams
A. McGregor · 2005
Earlier work this paper cites.
Improved approximation guarantees for weighted matching in the semi-streaming model
L. Epstein, A. Levin, J. Mestre, and D. Segev · 2011
Earlier work this paper cites.
On the communication and streaming complexity of maximum bipartite matching
A. Goel, M. Kapralov, and S. Khanna · 2012
Earlier work this paper cites.
Maximum matching in semi-streaming with few passes
C. Konrad, F. Magniez, and C. Mathieu · 2012
Earlier work this paper cites.
Linear programming in the semi-streaming model with application to the maximum matching problem
K. J. Ahn and S. Guha · 2013
Earlier work this paper cites.
Superlinear lower bounds for multipass graph processing
V. Guruswami and K. Onak · 2013
Earlier work this paper cites.
Better bounds for matchings in the streaming model
M. Kapralov · 2013
Earlier work this paper cites.
Improved streaming algorithms for weighted matching, via unweighted matching
M. Crouch and D. S. Stubbs · 2014
Earlier work this paper cites.
Approximating matching size from random streams
M. Kapralov, S. Khanna, and M. Sudan · 2014
Earlier work this paper cites.
Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints
K. J. Ahn and S. Guha · 2015
Earlier work this paper cites.
Fully dynamic matching in bipartite graphs
A. Bernstein and C. Stein · 2015
Cited alongside, same era.
Sublinear estimation of weighted matchings in dynamic data streams
M. Bury and C. Schwiegelshohn · 2015
Cited alongside, same era.
Parameterized streaming: Maximal matching and vertex cover
R. H. Chitnis, G. Cormode, M. T. Hajiaghayi, and M. Monemizadeh · 2015
Cited alongside, same era.
Maximum matching in turnstile streams
C. Konrad · 2015
Cited alongside, same era.
Maximum matchings in dynamic graph streams and the simultaneous communication model
S. Assadi, S. Khanna, Y. Li, and G. Yaroslavtsev · 2016
Cited alongside, same era.
Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams
R. Chitnis, G. Cormode, H. Esfandiari, M. Hajiaghayi, A. McGregor, M. Monemizadeh, and S. Vorotnikova · 2016
A (2 + epsilon)-approximation for maximum weight matching in the semi-streaming model
A. Paz and G. Schwartzman · 2017
Later among the works it cites.
Streaming algorithms for estimating the matching size in planar graphs and beyond
H. Esfandiari, M. Hajiaghayi, V. Liaghat, M. Monemizadeh, and K. Onak · 2018
Later among the works it cites.
A simple augmentation method for matchings with applications to streaming algorithms
C. Konrad · 2018
Later among the works it cites.
A simple, space-efficient, streaming algorithm for matchings in low arboricity graphs
A. McGregor and S. Vorotnikova · 2018
Later among the works it cites.
Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs
S. Assadi, M. Bateni, A. Bernstein, V. S. Mirrokni, and C. Stein · 2019
Later among the works it cites.
Towards a unified theory of sparsification for matching problems
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Finding large matchings in semi-streaming
H. Esfandiari, M. Hajiaghayi, and M. Monemizadeh · 2016
Cited alongside, same era.
Planar matching in streams revisited
A. McGregor and S. Vorotnikova · 2016
Cited alongside, same era.
On estimating maximum matching size in graph streams
S. Assadi, S. Khanna, and Y. Li · 2017
Cited alongside, same era.
The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs
G. Cormode, H. Jowhari, M. Monemizadeh, and S. Muthukrishnan · 2017
Cited alongside, same era.
Maximum matching in two, three, and a few more passes over graph streams
S. Kale and S. Tirodkar · 2017
Cited alongside, same era.
Negative association: definition, properties, and applications
D. Wajc
Cited in the paper.
S. Assadi and A. Bernstein · 2019
Later among the works it cites.
Weighted matchings via unweighted augmentations
B. Gamlath, S. Kale, S. Mitrovic, and O. Svensson · 2019
Later among the works it cites.
Simplified and space-optimal semi-streaming (2+epsilon)-approximate matching
M. Ghaffari and D. Wajc · 2019
Later among the works it cites.
Approximate maximum matching in random streams
A. Farhadi, M. T. Hajiaghayi, T. Mai, A. Rao, and R. A. Rossi · 2020
Closest in time.
Space efficient approximation to maximum matching size from uniform edge samples
M. Kapralov, S. Mitrovic, A. Norouzi-Fard, and J. Tardos · 2020
Closest in time.