Matroid-based TSP rounding for half-integral solutions
成果类型：
Article
署名作者：
Gupta, Anupam; Lee, Euiwoong; Li, Jason; Mucha, Marcin; Newman, Heather; Sarkar, Sherry
署名单位：
Carnegie Mellon University; University of Michigan System; University of Michigan; University of California System; University of California Berkeley; University of Warsaw
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-024-02065-4
发表日期：
2024
页码：
541-576
关键词：
摘要：
We show how to round any half-integral solution to the subtour-elimination relaxation for the TSP, while losing a less-than-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$-$$\end{document} 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.