Matroid-based TSP rounding for half-integral solutions

DOI10.1007/s10107-024-02065-4MaRDI QIDQ6589761

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

Publication date: 20 August 2024

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

half-integral solution, rounding algorithm

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• The salesman's improved tours for fundamental classes
• Negative dependence and the geometry of polynomials
• 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
• An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
• A Randomized Rounding Approach to the Traveling Salesman Problem

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