Matroid-based TSP rounding for half-integral solutions

DOI10.1007/S10107-024-02065-4MaRDI QIDQ6589761zbMATH OpenFDO

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

Publication date 20 August 2024

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

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S10107-024-02065-4

zbMATH Keywords

half-integral solution, rounding algorithm

Mathematics Subject Classification ID

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

Recommendations

• Matroid-based TSP rounding for half-integral solutions
• A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP
• An improved approximation algorithm for TSP in the half integral case
• Towards improving Christofides algorithm for half-integer TSP

Cites work

• 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
• An \(O(\log n/\log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
• An improved approximation algorithm for TSP in the half integral case
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• Heuristic analysis, linear programming and branch and bound
• scientific article; zbMATH DE number 3746840 (Why is no real title available?)
• Negative dependence and the geometry of polynomials
• On the Distribution of the Number of Successes in Independent Trials
• The salesman's improved tours for fundamental classes
• Towards improving Christofides algorithm for half-integer TSP

Cited in

(2)

• Maximum entropy is a 10/7-approximation algorithm for the TSP on half-integral cycle cut instances
• The integrality gap of the traveling salesman problem is \(\frac{4}{3}\) if the LP solution has at most \(n + 6\) non-zero components

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6589761)