Matroid-based TSP rounding for half-integral solutions

DOI10.1007/978-3-031-06901-7_23zbMath1497.90173arXiv2111.09290OpenAlexW3212193323MaRDI QIDQ2164710

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

Publication date: 16 August 2022

Full work available at URL: https://arxiv.org/abs/2111.09290

zbMATH Keywords

half-integral solutionmatroid intersection polytopesubtour-elimination relaxation

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (2)

A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP ⋮ A deterministic better-than-3/2 approximation algorithm for metric TSP

Cites Work

• Unnamed Item
• Unnamed Item
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• Worst-case analysis of a new heuristic for the travelling salesman problem
• On the Distribution of the Number of Successes in Independent Trials
• Heuristic analysis, linear programming and branch and bound
• An improved approximation algorithm for TSP in the half integral case
• 2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture
• A Randomized Rounding Approach to the Traveling Salesman Problem

This page was built for publication: Matroid-based TSP rounding for half-integral solutions