A lower bound for the max entropy algorithm for TSP

DOI10.1007/978-3-031-59835-7_18MaRDI QIDQ7030557zbMATH OpenFDO

Authors Billy Jin, Nathan Klein, David P. Williamson

Publication date 7 February 2025

Full work available at URL https://doi.org/10.1007/978-3-031-59835-7_18

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites work

• A (slightly) improved approximation algorithm for metric TSP
• A (slightly) improved bound on the integrality gap of the subtour LP for TSP
• A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP
• 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 Analysis of Several Heuristics for the Traveling Salesman Problem
• An experimental evaluation of the best-of-many Christofides' algorithm for the 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?)
• On two geometric problems related to the travelling 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 Minimum Spanning Trees
• Tight bounds for christofides' traveling salesman heuristic

Cited in

(1)

• Dual charging for half-integral TSP

This page was built for publication: A lower bound for the max entropy algorithm for TSP

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