Asymptotically Tight Fractional Online Matching Under Edge Arrivals

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\mathrm{/}2+\mathrm{\Theta }(1\mathrm{/}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.