Reproduce “(Optimal) Online Bipartite Matching with Degree Information” 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
Anders Aamand, Justin Y. Chen, Piotr Indyk
Researchers from MIT introduced a model for online graph problems that incorporates vertex degree predictions to inform algorithmic decisions. Their MinPredictedDegree (MPD) algorithm achieves stochastic dominance for online bipartite matching under the Chung-Lu-Vu Bipartite random graph model and demonstrates strong empirical performance on real-world and synthetic datasets, often exceeding 0.98 competitive ratio.
Key insights
- Vertex degree information, a simple and natural graph property, can serve as a highly effective predictor for enhancing online algorithm performance.
- The MinPredictedDegree (MPD) algorithm is theoretically optimal, exhibiting stochastic dominance, for online bipartite matching on graphs drawn from the Chung-Lu-Vu Bipartite random graph model when using expected degrees.
- While degree predictions significantly improve average-case performance, they do not inherently break the classical 1 - 1/e worst-case competitive ratio barrier for online bipartite matching.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.