Matroid-based TSP rounding for half-integral solutions

期刊论文
出版模式：

开放获取
发表日期：

2024年3月6日

查看全文

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

摘要

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.