Table of Contents: :: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Gupta, Anupam, Lee, Euiwoong, Li, Jason, Mucha, Marcin, Newman, Heather, Sarkar, Sherry
Format:	Preprint
Published:	2021
Subjects:	Data Structures and Algorithms
Online Access:	https://arxiv.org/abs/2111.09290
Tags:	Add Tag No Tags, Be the first to tag this record!

Table of Contents:

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.