Analysis of Christofides' heuristic: some paths are more difficult than cycles
From MaRDI portal
Publication:1180833
DOI10.1016/0167-6377(91)90016-IzbMath0748.90071OpenAlexW2162750432MaRDI QIDQ1180833
Publication date: 27 June 1992
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0167-6377(91)90016-i
heuristictravelling salesmanworst-case analysisHamiltonian pathminimum total lengthChristofides-like algorithms
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)
Related Items (63)
Approximation algorithms for the \(k\)-depots Hamiltonian path problem ⋮ On the Approximation Ratio of the Path Matching Christofides Algorithm ⋮ From symmetry to asymmetry: generalizing TSP approximations by parametrization ⋮ Approximation algorithms and heuristics for a 2-depot, heterogeneous Hamiltonian path problem ⋮ 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 ⋮ Approximation Algorithms for Not Necessarily Disjoint Clustered TSP ⋮ GRASP with path relinking for the symmetric Euclidean clustered traveling salesman problem ⋮ What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs ⋮ Constant factor approximation algorithm for TSP satisfying a biased triangle inequality ⋮ A note on approximation algorithms of the clustered 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 ⋮ The hierarchical Chinese postman problem: the slightest disorder makes it hard, yet disconnectedness is manageable ⋮ An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem ⋮ The median routing problem for simultaneous planning of emergency response and non-emergency jobs ⋮ An approximation algorithm for the clustered path travelling salesman problem ⋮ Approximation algorithms for the min-max clustered \(k\)-traveling salesmen problems ⋮ An LP-based approximation algorithm for the generalized traveling salesman path problem ⋮ An approximation algorithm for the clustered path travelling salesman problem ⋮ An extension of the Christofides heuristic for a single-depot multiple Hamiltonian path problem ⋮ Achieving feasibility for clustered traveling salesman problems using PQ‐trees ⋮ Beating the Integrality Ratio for $s$-$t$-Tours in Graphs ⋮ Routing open shop and flow shop scheduling problems ⋮ Approximation algorithms for the traveling repairman and speeding deliveryman problems ⋮ Scheduling on a graph with release times ⋮ The traveling salesman problem with flexible coloring ⋮ An improved approximation algorithm for the clustered traveling salesman problem ⋮ 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 ⋮ Improved Approximations for Hard Optimization Problems via Problem Instance Classification ⋮ Finding an approximate minimum-link visibility path inside a simple polygon ⋮ Tour recommendation for groups ⋮ On the Metric $s$--$t$ Path Traveling Salesman Problem ⋮ Balancing the stations of a self service “bike hire” system ⋮ Traveling salesman path problems ⋮ Approximation algorithms for multiple terminal, Hamiltonian path problems ⋮ \(\frac{13}{9}\)-approximation for graphic TSP ⋮ A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality ⋮ Vehicle routing with subtours ⋮ Approximating the multiple-depot multiple-terminal Hamiltonian path problem ⋮ Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s) ⋮ From symmetry to asymmetry: generalizing TSP approximations by parametrization ⋮ \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem ⋮ Approximation algorithms for general cluster routing problem ⋮ Cooperative TSP ⋮ Algorithms for Euclidean Degree Bounded Spanning Tree Problems ⋮ A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots ⋮ Reassembling Trees for the Traveling Salesman ⋮ Better \(s-t\)-tours by Gao trees ⋮ Structural Properties of Hard Metric TSP Inputs ⋮ An improved upper bound on the integrality ratio for the \(s\)-\(t\)-path TSP ⋮ On the Metric $s$--$t$ Path Traveling Salesman Problem ⋮ Differential approximation of NP-hard problems with equal size feasible solutions ⋮ Unnamed Item ⋮ A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids ⋮ Minimum Scan Cover with Angular Transition Costs ⋮ Approximation algorithms with constant ratio for general cluster routing problems ⋮ A \(\frac{5}{3}\)-approximation algorithm for the clusterd traveling salesman tour and path problems ⋮ Reducing Path TSP to TSP ⋮ An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem ⋮ Approximating minimum-cost connected \(T\)-joins
Cites Work
This page was built for publication: Analysis of Christofides' heuristic: some paths are more difficult than cycles
