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

Hoogeveen, J. A.

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




Related Items (63)

Approximation algorithms for the \(k\)-depots Hamiltonian path problemOn the Approximation Ratio of the Path Matching Christofides AlgorithmFrom symmetry to asymmetry: generalizing TSP approximations by parametrizationApproximation algorithms and heuristics for a 2-depot, heterogeneous Hamiltonian path problemA 3/2-Approximation for the Metric Many-Visits Path TSPA LP-based approximation algorithm for generalized traveling salesperson path problemBetter s-t-Tours by Gao TreesApproximation Algorithms for Not Necessarily Disjoint Clustered TSPGRASP with path relinking for the symmetric Euclidean clustered traveling salesman problemWhat would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTsConstant factor approximation algorithm for TSP satisfying a biased triangle inequalityA note on approximation algorithms of the clustered traveling salesman problemSlightly improved upper bound on the integrality ratio for the \(s - t\) path TSPImproving on best-of-many-Christofides for \(T\)-toursThe hierarchical Chinese postman problem: the slightest disorder makes it hard, yet disconnectedness is manageableAn experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problemThe median routing problem for simultaneous planning of emergency response and non-emergency jobsAn approximation algorithm for the clustered path travelling salesman problemApproximation algorithms for the min-max clustered \(k\)-traveling salesmen problemsAn LP-based approximation algorithm for the generalized traveling salesman path problemAn approximation algorithm for the clustered path travelling salesman problemAn extension of the Christofides heuristic for a single-depot multiple Hamiltonian path problemAchieving feasibility for clustered traveling salesman problems using PQ‐treesBeating the Integrality Ratio for $s$-$t$-Tours in GraphsRouting open shop and flow shop scheduling problemsApproximation algorithms for the traveling repairman and speeding deliveryman problemsScheduling on a graph with release timesThe traveling salesman problem with flexible coloringAn improved approximation algorithm for the clustered traveling salesman problemAn LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problemShorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphsImproved Approximations for Hard Optimization Problems via Problem Instance ClassificationFinding an approximate minimum-link visibility path inside a simple polygonTour recommendation for groupsOn the Metric $s$--$t$ Path Traveling Salesman ProblemBalancing the stations of a self service “bike hire” systemTraveling salesman path problemsApproximation algorithms for multiple terminal, Hamiltonian path problems\(\frac{13}{9}\)-approximation for graphic TSPA 4-approximation algorithm for the TSP-path satisfying a biased triangle inequalityVehicle routing with subtoursApproximating the multiple-depot multiple-terminal Hamiltonian path problemApproximation 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 problemApproximation algorithms for general cluster routing problemCooperative TSPAlgorithms for Euclidean Degree Bounded Spanning Tree ProblemsA 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of DepotsReassembling Trees for the Traveling SalesmanBetter \(s-t\)-tours by Gao treesStructural Properties of Hard Metric TSP InputsAn improved upper bound on the integrality ratio for the \(s\)-\(t\)-path TSPOn the Metric $s$--$t$ Path Traveling Salesman ProblemDifferential approximation of NP-hard problems with equal size feasible solutionsUnnamed ItemA push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroidsMinimum Scan Cover with Angular Transition CostsApproximation algorithms with constant ratio for general cluster routing problemsA \(\frac{5}{3}\)-approximation algorithm for the clusterd traveling salesman tour and path problemsReducing Path TSP to TSPAn Improved Approximation Algorithm for The Asymmetric Traveling Salesman ProblemApproximating minimum-cost connected \(T\)-joins



Cites Work


This page was built for publication: Analysis of Christofides' heuristic: some paths are more difficult than cycles