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.

1. Conduct a comprehensive literature review:

The project will involve an in-depth study of existing research papers, academic articles, and relevant publications on the topic of online stochastic matching.  This literature evaluation will be a strong starting point for assessing the state of knowledge today and identifying knowledge gaps regarding sample complexity.


2. Refine the existing sample complexity bound:

Building on existing work by Guo, Huang, Tang, and Zhang [1], this project aims to develop new insights and mathematical proofs to refine sample complexity constraints for online random matching problems. By utilizing statistical knowledge and mathematical techniques, the project seeks to provide a more accurate estimate of the sample complexity of the problem.


3. Document and communicate the research:

It would also be desirable to produce a comprehensive and well-structured study report outlining the methodology, results and implications of the study. The research will also endeavor to communicate the results of the research in a clear and understandable manner, facilitating information-sharing and possible future work.


By achieving these objectives, this final year project intends to contribute to the existing body of knowledge on the sample complexity of online stochastic matching problem. The results of this research will not only deepen the understanding of the problem, but will also have a practical impact on areas such as online advertising, where efficient matching algorithms are essential for effectively targeting users and maximizing benefits to advertisers.

Scroll to Top