TY - GEN
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:
© 2022, Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
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, and a new 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, and a new use of max-entropy sampling, can give better guarantees.
UR - http://www.scopus.com/inward/record.url?scp=85131922293&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85131922293&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-06901-7_23
DO - 10.1007/978-3-031-06901-7_23
M3 - Conference contribution
AN - SCOPUS:85131922293
SN - 9783031069000
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 305
EP - 318
BT - Integer Programming and Combinatorial Optimization - 23rd International Conference, IPCO 2022, Proceedings
A2 - Aardal, Karen
A2 - Sanità, Laura
PB - Springer Science and Business Media Deutschland GmbH
T2 - 23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022
Y2 - 27 June 2022 through 29 June 2022
ER -