Matroid-Based TSP Rounding for Half-Integral Solutions

Anupam Gupta, Euiwoong Lee, Jason Li +3

We show how to round any half-integral solution to the subtour-elimination relaxation for the TSP, while losing a less-than-1.5 factor. Such a rounding algorithm was recently given…