A 43 -approximation algorithm for half-integral cycle cut instances of the TSP

DOI10.1007/S10107-025-02193-5MaRDI QIDQ7019063zbMATH OpenFDO

Authors Billy Jin, Nathan Klein, David P. Williamson

Publication date 5 March 2025

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

Full work available at URL https://doi.org/10.1007/S10107-025-02193-5

zbMATH Keywords

approximation algorithmcycle cutgraph algorithmhalf-integral cycleintegrality gapsubtour LPtraveling salesman problemTSP

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59) Abstract computational complexity for mathematical programming problems (90C60)

Cites work

• 2-matchings, the traveling salesman problem, and the subtour LP: a proof of the Boyd-Carr conjecture
• A (slightly) improved approximation algorithm for metric TSP
• A (slightly) improved bound on the integrality gap of the subtour LP for TSP
• An improved approximation algorithm for TSP in the half integral case
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• Building Chain and Cactus Representations of All Minimum Cuts from Hao–Orlin in the Same Asymptotic Run Time
• Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
• Finding the exact integrality gap for small traveling salesman problems
• Hard to solve instances of the Euclidean traveling salesman problem
• Heuristic analysis, linear programming and branch and bound
• scientific article; zbMATH DE number 1187146 (Why is no real title available?)
• scientific article; zbMATH DE number 3746840 (Why is no real title available?)
• Matroid-based TSP rounding for half-integral solutions
• Network flow algorithms
• Removing and adding edges for the traveling salesman problem
• Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs
• Solution of a Large-Scale Traveling-Salesman Problem
• The salesman's improved tours for fundamental classes
• The traveling salesman problem and its variations.
• The Traveling-Salesman Problem and Minimum Spanning Trees
• Towards improving Christofides algorithm for half-integer TSP
• Worst-case comparison of valid inequalities for the TSP

Cited in

(1)

• Maximum entropy is a 10/7-approximation algorithm for the TSP on half-integral cycle cut instances

This page was built for publication: A \(\frac{4}{3} \)-approximation algorithm for half-integral cycle cut instances of the TSP

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