Matroid-based TSP rounding for half-integral solutions

Anupam Gupta, Euiwoong Lee, Jason Li, Marcin Mucha, Heather Newman, Sherry Sarkar

Research output: Contribution to journalArticlepeer-review

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, combined with a novel use of max-entropy sampling, can give better guarantees.

Original languageEnglish (US)
JournalMathematical Programming
DOIs
StateAccepted/In press - 2024

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Matroid-based TSP rounding for half-integral solutions'. Together they form a unique fingerprint.

Cite this