Eight-Fifth Approximation for the Path TSP
From MaRDI portal
Publication:4911537
DOI10.1007/978-3-642-36694-9_31zbMath1336.90098arXiv1209.3523MaRDI QIDQ4911537
Publication date: 19 March 2013
Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1209.3523
matchingpolyhedronapproximation algorithmtraveling salesman problem\(T\)-joinpath TSPtree (basis) polytope
90C35: Programming involving graphs or networks
90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C59: Approximation methods and heuristics in mathematical programming
90C27: Combinatorial optimization
68W25: Approximation algorithms
Related Items
On the Metric $s$--$t$ Path Traveling Salesman Problem, A 3/2-Approximation for the Metric Many-Visits Path TSP, TSP Tours in Cubic Graphs: Beyond 4/3, On the Metric $s$--$t$ Path Traveling Salesman Problem, Reducing Path TSP to TSP, An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem, Unnamed Item, Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center, Beating the Integrality Ratio for $s$-$t$-Tours in Graphs, Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) 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, Approximation algorithms for the bus evacuation problem, Better \(s-t\)-tours by Gao trees, A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality, Approximation algorithms for general cluster routing problem, Approximation algorithms with constant ratio for general cluster routing problems, A LP-based approximation algorithm for generalized traveling salesperson path problem, \(\frac{13}{9}\)-approximation for graphic TSP, An improved upper bound on the integrality ratio for the \(s\)-\(t\)-path 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, Slightly improved upper bound on the integrality ratio for the \(s - t\) path TSP, Improving on best-of-many-Christofides for \(T\)-tours, An LP-based approximation algorithm for the generalized traveling salesman path problem, Reassembling Trees for the Traveling Salesman, On the Clustered Steiner Tree Problem, Better s-t-Tours by Gao Trees
