← Back to all news
arXiv AI By Jingtao Tang, Hang Ma

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

Read the original on arXiv AI →

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.

Machine-generated by The Flow from the publisher's headline and feed description — not written or checked by a human. The full article lives at arXiv AI.

Related stories

arXiv Machine Learning
Aug 5

Beyond Solving: Prescriptive Probing for Neural Routing Solvers

arXiv:2602. 07216v2 Announce Type: replace Abstract: Neural combinatorial optimization (NCO) trains fast heuristics for routing problems, but planners often need more than a single solve: they ask which stop to drop, which transition to preserve, or which subset of stops to remove if a route is infeasible.

By Reuben Narad, L\'eonard Boussioux, Michael Wagner
reinforcement-learningbenchmarkssafety
More like this →
arXiv AI
Aug 26

Pivot-and-Station Multi-Agent Path Finding: Solvability, Complexity, and Algorithms

The paper introduces Pivot-and-Station Multi-Agent Path Finding (PS‑MAPF), a variant of MAPF where a subset of agents must visit interchangeable pivots before all agents occupy anonymous stations. It provides a full solvability characterization: every instance on a 2‑edge‑connected graph is solvable, and for arbitrary connected graphs a structural effective‑distance measure relative to unoccupied vertices gives a necessary and sufficient condition. The authors prove that minimizing station‑makespan or station‑flowtime is NP‑hard even with a single pivot, and present three algorithms—a complete baseline, a SAT‑based optimal solver, and Pivot‑Prioritized Planning (PPP), which solves 74‑89% of benchmark instances with significantly lower makespan and flowtime than the baseline.

By Andrea Di Nezza, Mihir Patel, Fabio Fagnani, Sara Bernardini
agentsroboticsbenchmarks
More like this →