Asymptotically Tight Fractional Online Matching Under Edge Arrivals
2026-08-24 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors solved a math problem about how well computers can match pairs online as data comes in, focusing on fractional matches. They found the best possible performance ratio is about 1/2 plus a small term that depends on the size of the problem. Interestingly, their method was originally suggested by OpenAI's ChatGPT. The authors refined the explanation through a discussion and take full responsibility for any mistakes.
fractional online matchingcompetitive ratioedge arrivalsalgorithm analysisasymptotic boundsonline algorithmsmatching theoryfractional matchingsChatGPT
Authors
David Wajc
Abstract
In this brief note, we close the asymptotic gap between known upper and lower bounds for fractional online matching under edge arrivals. We prove that the optimal competitive ratio for this problem is $1/2+Θ(1/n)$. The algorithm was suggested and analyzed by OpenAI's ChatGPT Sol based on a single prompt. The presentation was streamlined over a few hours, based on a back and forth discussion with the author, who assumes responsibility for any errors.