arXiv AI

Probabilistic Focal Search: Accelerating Bounded-Suboptimal Search via Lower-Bound Advancement

Probabilistic Focal Search (PFS) augments traditional Focal Search by probabilistically choosing between the standard heuristic-guided expansion and expanding the minimum‑f node in OPEN. This strategy advances the lower bound, enlarges the FOCAL frontier, and can dramatically reduce node expansions—up to 90% in some benchmarks such as N‑Puzzle and TSP—especially when long f_min plateaus delay useful FOCAL admissions. An anytime variant, APFS, outperforms other tested anytime algorithms on the Generalized Covering TSP, and the same probabilistic scheduler transfers to Dynamic Potential Search as Probabilistic Dynamic Potential Search (PDPS), though its effectiveness varies by domain and bound.

arXiv AI
Aug 24

Unified Branch-and-Bound Search for the Steiner Traveling Salesman Problem on Graphs of Convex Sets

The paper introduces a unified branch‑and‑bound framework for the Steiner Traveling Salesman Problem on Graphs of Convex Sets (GCS), where the goal is to find a minimum‑cost closed walk through required convex sets while allowing optional vertices and revisits. The method uses additive lower‑bound graph costs for committed prefixes and a cut‑separated connected‑flow relaxation for the remaining cost, guaranteeing finite termination under a uniform positive‑cost assumption. Experiments on benchmark instances show that both best‑first and depth‑first traversal strategies find feasible solutions within 30 seconds, achieving mean certified optimality gaps of 28.1% and 29.7% respectively, outperforming two recent baselines.

By Jingtao Tang, Hang Ma
arXiv Machine Learning
Sep 30

Local Search with Correlated Randomness

arXiv:2607.17469v2 Announce Type: replace-cross Abstract: How much does an algorithm's running-time distribution under independent randomness reveal about its behavior when independence is no longer...

By Yunbei Xu
arXiv AI
Sep 25

Canopy: Exploiting Piecewise Smooth Tree Priors for Multi-Fidelity Bandits

CANOPY is a multi‑fidelity tree bandit algorithm that learns where a piecewise‑smooth prior holds instead of assuming global smoothness. It uses cheap random‑path probes to certify local aggregation bias and then focuses expensive leaf evaluations on cells where smoothness is violated. The method achieves provable fixed‑budget and regret guarantees that scale with the number of discontinuities, matching smooth‑tree rates when no violations exist and approaching structure‑blind search when violations are dense.

By Michael Jerge, Suman Jana
arXiv AI
3d ago

Ballad: Bandit-Based LLM Routing for Automated Heuristic Discovery

Ballad is an online bandit algorithm that orchestrates a pool of large language models (LLMs) to improve automated heuristic discovery for NP‑hard combinatorial optimization problems. By selecting models adaptively, propagating credit through a DAG of heuristic genealogy, and discounting stale observations, Ballad matches or exceeds the best single LLM while reducing API costs by up to 65.6%. The study challenges the assumption that larger, more expensive models always yield better heuristics, showing that a well‑managed ensemble can outperform any individual model.

By Samidha Verma, Ankit Anand, Sayan Ranu
arXiv AI
Oct 19

Hard Instances on Demand

The paper presents a method for generating hard problem instances by treating instance creation as an optimization problem, using solver runtime as the objective. Leveraging the Nevergrad platform, the authors generate challenging instances for four NP‑hard problems—satisfiability, traveling salesperson, Hamiltonian cycle, and non‑permutation flow‑shop scheduling—that outperform random draws and rival curated benchmark sets. The approach requires only a solver, an instance encoder, and a compute budget, and it can uncover structural insights such as phase‑transition behavior in SAT.

By Jamie Fravel, Martin Kouteck\'y, Pavlo Tsitsei
arXiv Machine Learning
Sep 22

Leveraging Inference-Time Compute for Diffusion Models via Global Scheduling of Denoising Trajectories

The paper studies how to allocate a fixed computational budget across the denoising steps of diffusion models to improve sample quality at deployment. It shows that the expected benefit of evaluating multiple candidates at a step can be decomposed into a step‑specific sensitivity and a universal sample‑size factor, and that the optimal allocation follows a water‑filling structure. Experiments demonstrate that this allocation achieves the same quality as a uniform strategy while reducing function evaluations by 20–50%.

By Yuan Cao, Yifu Tang, Hangqi Li, Zeyu Zheng