139-approximation for graphic TSP
From MaRDI portal
Publication:2904746
Recommendations
Cited in
(24)- The approximation ratio of the greedy algorithm for the metric traveling salesman problem
- Constant factor approximation for ATSP with two edge weights
- Matroid-based TSP rounding for half-integral solutions
- \(\frac{13}{9}\)-approximation for graphic TSP
- Approximating minimum-cost connected \(T\)-joins
- An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
- The traveling salesman problem on cubic and subcubic graphs
- Overview of new approaches for approximating TSP
- An improved analysis of the Mömke-Svensson algorithm for graph-TSP on subquartic graphs
- Graph-TSP from Steiner cycles
- Removing and adding edges for the traveling salesman problem
- Constant factor approximation for ATSP with two edge weights (extended abstract)
- scientific article; zbMATH DE number 6347354 (Why is no real title available?)
- Approximation hardness of graphic TSP on cubic graphs
- 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
- New inapproximability bounds for TSP
- An improved approximation algorithm for TSP in the half integral case
- TSP tours in cubic graphs: beyond 4/3
- Approximating the regular graphic TSP in near linear time
- A deterministic better-than-3/2 approximation algorithm for metric TSP
- Sublinear algorithms for TSP via path covers
- On polynomial kernels for traveling salesperson problem and its generalizations
- Improved approximation algorithms for (1,2)-TSP and Max-TSP using path covers in the semi-streaming model
- Dual charging for half-integral TSP
This page was built for publication: \(\frac {13}{9}\)-approximation for graphic TSP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2904746)
