# Augmented Graphs of Convex Sets and the Traveling Salesman Problem

arXiv: https://arxiv.org/abs/2604.06406 · HTML: https://mlsanity.com/paper/2604.06406/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Apr 2026.

## Built on by (most cited first, 1 of 1)

- [Unified Branch-and-Bound Search for the Steiner Traveling Salesman Problem on Graphs of Convex Sets](https://mlsanity.com/paper/2608.21319/) (2026)

## Abstract (arXiv)

We present a trajectory optimization algorithm for the traveling salesman problem (TSP) in graphs of convex sets (GCS). Our framework uses an augmented graph of convex sets to encode the TSP specification and solve it exactly as a shortest path problem in GCS. We establish a precise relationship between the landmark Bellman-Held-Karp algorithm and the augmented graph of convex sets with a TSP specification. Additionally, we present a branch and bound heuristic that uses minimum 1-trees to obtain certifiably optimal or near optimal solutions and scales to problems far larger than the exact framework can handle. To assess and certify performance, we explore several alternative lower bounds.