Objectives
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.
Methodologies
— how the project is going to be implemented -
Literature Review
Analyze & Summarize
Theoretical Framework
Familiarize & Explore
Documentation and Reporting
Organize & Prepare
Progress
Inception
October 1, 2023
Elaboration
January 21, 2024
Exhibition
April 23, 2024
Finalization
April 26, 2023
Results
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.