2020/05/17 by Eleni C. Akrida, Akrida, Eleni C., Argyrios Deligkas +7
Computer Science · Mathematics · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2005.08263
openalex publication_date 2020/05/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper studies the maximum cardinality matching problem in stochastically evolving graphs. We formally define the arrival-departure model with stochastic departures. There, a graph is sampled from a specific probability distribution and it is revealed as a series of snapshots. Our goal is to study algorithms that create a large matching in the sampled graphs. We define the price of stochasticity for this problem which intuitively captures the loss of any algorithm in the worst case in the size of the matching due to the uncertainty of the model. Furthermore, we prove the existence of a deterministic optimal algorithm for the problem. In our second set of results we show that we can efficiently approximate the expected size of a maximum cardinality matching by deriving a fully randomized approximation scheme (FPRAS) for it. The FPRAS is the backbone of a probabilistic algorithm that is optimal when the model is defined over two timesteps. Our last result is an upper bound of (2)/(3) on the price of stochasticity. This means that there is no algorithm that can match more than (2)/(3) of the edges of an optimal matching in hindsight.