Eight-Fifth Approximation for the Path TSP

DOI10.1007/978-3-642-36694-9_31zbMath1336.90098arXiv1209.3523OpenAlexW3101686738MaRDI QIDQ4911537

András Sebő

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

zbMATH Keywords

matchingpolyhedronapproximation algorithmtraveling salesman problem\(T\)-joinpath TSPtree (basis) polytope

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (28)

A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ A LP-based approximation algorithm for generalized traveling salesperson path problem ⋮ 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 ⋮ 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 ⋮ Unnamed Item ⋮ An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph 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 ⋮ On the Metric $s$--$t$ Path Traveling Salesman Problem ⋮ \(\frac{13}{9}\)-approximation for graphic TSP ⋮ A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality ⋮ Approximation algorithms for general cluster routing problem ⋮ TSP Tours in Cubic Graphs: Beyond 4/3 ⋮ Approximation algorithms for the bus evacuation problem ⋮ Reassembling Trees for the Traveling Salesman ⋮ Better \(s-t\)-tours by Gao trees ⋮ An improved upper bound on the integrality ratio for the \(s\)-\(t\)-path TSP ⋮ On the Metric $s$--$t$ Path Traveling Salesman Problem ⋮ Approximation algorithms with constant ratio for general cluster routing problems ⋮ Reducing Path TSP to TSP ⋮ An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem ⋮ Approximating minimum-cost connected \(T\)-joins ⋮ On the Clustered Steiner Tree Problem

This page was built for publication: Eight-Fifth Approximation for the Path TSP