Matroid-Based TSP Rounding for Half-Integral Solutions

2021/11/17 by Gupta, Anupam, Lee, Euiwoong, Li, Jason +3 · 3 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2111.09290

Abstract

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 by Karlin, Klein, and Oveis Gharan based on sampling from max-entropy distributions. We build on an approach of Haddadan and Newman to show how sampling from the matroid intersection polytope, and a new use of max-entropy sampling, can give better guarantees.

Cited by

• TSP integrality gap via 2-edge-connected multisubgraph problem under coincident IP optima
• Dual Charging for Half-Integral TSP
• The Integrality Gap of the Traveling Salesman Problem is 4/3 if the LP Solution Has at Most n+6 Non-zero Components

Related

• A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP
• Dependent Randomized Rounding for Matroid Polytopes and Applications
• Dual Charging for Half-Integral TSP
• A Lower Bound for the Max Entropy Algorithm for TSP
• Rounding Sum-of-Squares Relaxations