Double Pairing: Maximum Edge-Weighted Online Matching with Uniformly-Drawn Vertex Arrivals

Abstract

This thesis examines the problem of maximimum edge-weighted online perfect matching on complete graphs with independently and uniformly drawn vertices. In our model, n students equally likely to be any of m types arrive one at a time to a classroom where they are paired o by the professor. The professor knows the total number of students that will attend, the types of students that may attend, and the utility between students of any particular pair of types. Lastly, because of COVID-19 guidelines, the professor can only allow k students at one time in without irreversibly assigning a pair. This is a unique feature of our interpretation of the problem. We attempt to perfectly match students so as to maximize the sum of pairwise utilities in expectation. We analyze two online algorithms in terms of their competitive ratio with the offline optimum. We show that Double Pairing achieves a competitive ratio of Ω 2k m

. Lastly, we upper bound the performance of any online algorithm, demonstrating that this competitive ratio is optimal.