Research map / Probabilistic and scientific modeling / Variational and generative sampling
Revisiting Sampling for Combinatorial Optimization
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 |
|---|---|---|---|
| Replace Gibbs sampling with PAS (path auxiliary sampler) based parallel sampling (ablation) | iSCO sampler on MIS and MAXCUT · Largest MIS and maxcut graphs | sample efficiency (steps to reach similar quality): ~100x more sample efficient | Helped |
| Reduce number of sampling steps 10x (shorter chain) (ablation) | iSCO on MIS and TSP · Largest MIS and TSP graphs | solution quality | No clear effect |
| Increase number of parallel Markov chains from 1 to 64 (ablation) | iSCO on MIS and TSP · Largest MIS and TSP graphs | solution quality | No clear effect |
| Choice of initial temperature (ablation) | iSCO · MIS and TSP | solution quality | Mixed |
| Annealing schedule type (ablation) | iSCO · MIS and TSP | convergence speed | Mixed |
| Use iSCO sampling (gradient-approximated ratios, PAS) instead of learning-based solvers for MIS | MIS on SATLIB and ER graphs · DIMES MIS benchmark | solution size | Helped |
| Use iSCO sampling instead of KaMIS for MIS on ER graphs | MIS on ER graphs · ER-[700-800] and ER-[9000-11000] | solution size: 45.15 vs 44.87 (ER-700-800); 384.20 vs 381.31 (ER-9000-11000) | Helped |
| Use iSCO sampling instead of KaMIS for MIS on SATLIB | MIS on SATLIB · SATLIB | solution size: 424.16 vs 425.96 | Hurt |
| Use iSCO sampling instead of learning-based methods for max clique | max clique on RB test graphs · RBtest | approximation ratio: 0.857 vs 0.789 (RUN-CSP) | Helped |
| Use iSCO sampling for maxcut on Optsicom | maxcut on Optsicom · Optsicom | approximation ratio: 1.00 vs 0.978 (S2V-DQN) | Helped |
| Use iSCO sampling for balanced graph partition | balanced graph partition on computation graphs · Inception-v3 and others | edge cut ratio: 0.05 vs 0.04 (GAP) | Hurt |
| Use iSCO sampling instead of DIMES for TSP | 2D-TSP · TSP-500/1000/10000 | tour length: 16.64 vs 16.84; 23.33 vs 23.69; 74.02 vs 74.06 | Helped |
Closest papers by meaning
- Cakewalk Sampling (AAAI 2020 · similarity 0.90)
- Regularized Langevin Dynamics for Combinatorial Optimization (ICML 2025 · similarity 0.87)
- Bayesian Optimization of Functions over Node Subsets in Graphs (NeurIPS 2024 · similarity 0.87)
- Efficient Combinatorial Optimization via Heat Diffusion (NeurIPS 2024 · similarity 0.87)
- Symmetric Replay Training: Enhancing Sample Efficiency in Deep Reinforcement Learning for Combinatorial Optimization (ICML 2024 · similarity 0.86)
- Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization (ICML 2024 · 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.