Research map / Learning theory and algorithms / Combinatorial and search optimization
An Improved Generic Bet-and-Run Strategy with Performance Prediction for Stochastic Local Search
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 |
|---|---|---|---|
| use diminishing-returns decision maker instead of currentBest to pick the run to continue | Bet-and-run (k=40, m=1, t1=0.4t) · MVC, t=2s | instances significantly better/worse vs F17: 43 better vs 24 worse | Helped |
| use perceptron or diminishing decision maker instead of currentBest | Bet-and-run on TSP, t=2000s · TSP | instances where benchmark better vs beaten: benchmark better on 3 instances, beaten on 19 | Helped |
| use more elaborate predictors instead of currentBest with k=4 initial runs | Bet-and-run · MVC and TSP, small and large budgets | statistical comparison vs F17 k=4 | Helped |
| increase total time budget t from small to large | predictor-based bet-and-run on MVC · MVC | advantage over F17 | Hurt |
| add a bet-and-run continuation phase versus a single full-budget run or independent restarts | currentBest bet-and-run · MVC and TSP, short budgets | significance vs EVEN/LUBY restarts | Helped |
| continue m=2 runs instead of m=1 | bet-and-run · MVC and TSP | score vs single run | Mixed |
| set decision-maker time t2 to 0 (ignore its cost) (ablation) | perceptron decision makers · MVC and TSP | score | No clear effect |
| perceptron-based decision makers instead of currentBest | bet-and-run k=40, m=1, EVEN · MVC t1 in {40s,100s,400s}; TSP t1=400s | score vs single run | Helped |
Closest papers by meaning
- A Generic Bet-and-Run Strategy for Speeding Up Stochastic Local Search (AAAI 2017 · similarity 0.93)
- Random is Faster than Systematic in Multi-Objective Local Search (AAAI 2026 · similarity 0.87)
- Local Bayesian optimization via maximizing probability of descent (NeurIPS 2022 · similarity 0.87)
- The Behavior and Convergence of Local Bayesian Optimization (NeurIPS 2023 · similarity 0.87)
- Minimizing UCB: a Better Local Search Strategy in Local Bayesian Optimization (NeurIPS 2024 · similarity 0.85)
- Learning Augmented Exact Exponential Algorithms (NeurIPS 2026 · similarity 0.85)
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.