Reproduce “Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Abhishek Dhawan, Eren C. Kızıldağ, Neeladri Maitra, Cheng Mao, Timothy L. H. Wee
The authors show that a simple greedy algorithm finds large induced matchings as a random graph is revealed vertex by vertex. In G(n,p), it finds at least (1/2−ε)L edges with high probability. Every online algorithm in the stated density range exceeds (1/2+ε)L only with exponentially small probability, establishing the half-scale barrier for this online model.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.