Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning What to Defer for Maximum Independent Sets
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Allow multiple vertex decisions per stage by deferring unresolved vertices (ablation) | LwD for MIS · ER (50–100 vertices) | validation score | Helped |
| Increase the maximum number of MDP iterations (ablation) | LwD for MIS · ER (50–100 vertices) | validation score | Helped |
| Add direct solution diversification reward (ablation) | LwD for MIS · ER (50–100 vertices) | validation score | Helped |
| Combine entropy bonus with the diversification reward (ablation) | LwD for MIS · ER (50–100 vertices) | validation score | Helped |
| Use entropy regularization alone instead of direct solution diversification (ablation) | LwD for MIS · ER (50–100 vertices) | final solution deviation | Hurt |
| Add direct solution diversification reward (ablation) | LwD for MIS · ER (50–100 vertices) | final solution deviation | Helped |
| Add 2-improvement local search (ablation) | LwD · REDDIT-M-12K | MIS objective: 292.6 -> 303.5 | Helped |
| Add 2-improvement local search (ablation) | LwD · BA (2 000 000 vertices) | MIS objective: 915 887 -> 915 968 | Helped |
| Use LwD instead of KaMIS under the reported time budget | MIS solvers · BA (2 000 000 vertices) | MIS objective: 909 988 -> 915 887 | Helped |
| Use LwD instead of KaMIS | MIS solvers · WS (500 000 vertices) | MIS objective: 157 298 -> 155 574 | Hurt |
| Use LwD instead of S2V-DQN | MIS solvers · Citation-Cora | approximation ratio: 0.96 -> 1.00 | Helped |
| Apply LwD to maximum weighted independent set | LwD · MWIS, ER (400–500 vertices) | objective: 34.29 -> 39.21 | Helped |
Closest papers by meaning
- Symmetric Replay Training: Enhancing Sample Efficiency in Deep Reinforcement Learning for Combinatorial Optimization (ICML 2024 · similarity 0.88)
- Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization (ICML 2025 · similarity 0.88)
- Differentiable Quadratic Optimization For the Maximum Independent Set Problem (ICML 2025 · similarity 0.87)
- GOAL: A Generalist Combinatorial Optimization Agent Learner (ICLR 2025 · similarity 0.87)
- Structured Reinforcement Learning for Combinatorial Decision-Making (NeurIPS 2025 · similarity 0.86)
- PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimization (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.