Sample Complexity of Online Stochastic Matching

A research-based final year project


By exploring the theoretical foundations and existing literature, the project aims to refine and enhance the understanding of the sample complexity bound in this domain.


— how the project is going to be implemented -

Literature Review

Analyze & Summarize

Theoretical Framework

Familiarize & Explore

Documentation and Reporting

Organize & Prepare



October 1, 2023


January 21, 2024


April 23, 2024


April 26, 2023


This project presents recent progress in understanding the sample complexity of the online stochastic matching problem, offering an updated upper bound that achieves a reduction by a factor of n-squared compared to previous works, where n stands for the number of online vertices. A more generalized bound for non-i.i.d. distribution online stochastic matching problem is also provided. Subsequently, the possibility of further reducing the bound through the parameter k (the total type of online vertices) is examined, and future suggestions on reducing the dependence on k through graph sparsification were made.

Scroll to Top