Two Algebraic Thresholds for Relaxations of Stable Metric TSP
Bilu–Linial stability asks whether an optimal solution remains uniquely optimal after every independent multiplicative increase of the input costs by a prescribed factor. For symmetric metric TSP, every 1.8-stable instance is solvable in polynomial time, and both the subtour relaxation and the weaker degree-only cycle-...