An analysis of the extended Christofides heuristic for the \(k\)-depot TSP

DOI10.1016/j.orl.2011.03.002zbMath1219.90149OpenAlexW2056897184MaRDI QIDQ635520

Brian Rodrigues, Zhou Xu, Liang Xu

Publication date: 19 August 2011

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2011.03.002

zbMATH Keywords

TSPapproximation algorithmsChristofides heuristicmultiple depots

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items

Approximation algorithms for the \(k\)-depots Hamiltonian path problem, Approximation algorithms for multi-vehicle stacker crane problems, Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees, An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem, Approximating the multiple-depot multiple-terminal Hamiltonian path problem, Exact and heuristic algorithms for routing AGV on path with precedence constraints, A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots, The \(m\)-Steiner traveling salesman problem with online edge blockages, An asymptotically tight online algorithm for \(m\)-steiner traveling salesman problem, A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms

Cites Work

• Unnamed Item
• A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem
• A variation of the generalized assignment problem arising in the New Zealand dairy industry
• A tabu search heuristic for the multi-depot vehicle routing problem
• \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem
• An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• New assignment algorithms for the multi-depot vehicle routing problem
• Arc Routing Problems, Part I: The Chinese Postman Problem
• Approximations for minimum and min-max vehicle routing problems
• Combinatorial optimization. Theory and algorithms.