TY - JOUR
T1 - Matroid-based TSP rounding for half-integral solutions
AU - Gupta, Anupam
AU - Lee, Euiwoong
AU - Li, Jason
AU - Mucha, Marcin
AU - Newman, Heather
AU - Sarkar, Sherry
N1 - Publisher Copyright:
© The Author(s) 2024.
PY - 2024/7
Y1 - 2024/7
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85186885664&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85186885664&partnerID=8YFLogxK
U2 - 10.1007/s10107-024-02065-4
DO - 10.1007/s10107-024-02065-4
M3 - Article
AN - SCOPUS:85186885664
SN - 0025-5610
VL - 206
SP - 541
EP - 576
JO - Mathematical Programming
JF - Mathematical Programming
IS - 1-2
ER -