Reproduce “Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set” 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
Yikai Wu, Haoyu Zhao, Sanjeev Arora
A comprehensive empirical study compared various contemporary AI-inspired algorithms against state-of-the-art classical heuristics for the Maximum Independent Set problem, demonstrating that AI methods consistently failed to outperform classical solvers and often performed worse than simple greedy heuristics, particularly on larger and denser graphs.
Key insights
- High-performing classical and some AI-inspired algorithms exhibit a sophisticated decision-making pattern: initial exploration or complex choices, followed by a transition towards simple greedy selections in later stages of solution construction.
- The current generation of AI-inspired algorithms for MIS, despite requiring substantial computational resources (GPU, training time), generally struggles with scalability and fails to leverage these resources to achieve superior solution quality compared to efficient classical CPU-based methods.
- Theoretical asymptotic conjectures regarding MIS algorithm performance on random graphs may not accurately reflect empirical behavior on practically sized graphs, indicating a gap between theoretical guarantees and observed performance.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.