Reassembling Trees for the Traveling Salesman

DOI10.1137/15M1010531zbMath1345.90079arXiv1502.03715MaRDI QIDQ2806177

Jens Vygen

Publication date: 17 May 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmspanning treetraveling salesman problem\(s\)-\(t\)-path TSP

Mathematics Subject Classification ID

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

Related Items (12)

A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ Better s-t-Tours by Gao Trees ⋮ Slightly improved upper bound on the integrality ratio for the \(s - t\) path TSP ⋮ Improving on best-of-many-Christofides for \(T\)-tours ⋮ An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem ⋮ An LP-based approximation algorithm for the generalized traveling salesman path problem ⋮ On the Metric $s$--$t$ Path Traveling Salesman Problem ⋮ A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality ⋮ Better \(s-t\)-tours by Gao trees ⋮ An improved upper bound on the integrality ratio for the \(s\)-\(t\)-path TSP ⋮ Reducing Path TSP to TSP ⋮ An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• The ellipsoid method and its consequences in combinatorial optimization
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• \(\frac{13}{9}\)-approximation for graphic TSP
• Approximating minimum-cost connected \(T\)-joins
• An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem
• An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
• New Inapproximability Bounds for TSP
• Better s-t-Tours by Gao Trees
• Heuristic analysis, linear programming and branch and bound
• Matching, Euler tours and the Chinese postman
• Eight-Fifth Approximation for the Path TSP
• Solution of a Large-Scale Traveling-Salesman Problem
• Improving christofides' algorithm for the s-t path TSP
• A Randomized Rounding Approach to the Traveling Salesman Problem
• Approximating Graphic TSP by Matchings
• On the Metric $s$--$t$ Path Traveling Salesman Problem
• The Traveling-Salesman Problem and Minimum Spanning Trees

This page was built for publication: Reassembling Trees for the Traveling Salesman