An analysis of the extended Christofides heuristic for the \(k\)-depot TSP
From MaRDI portal
Publication:635520
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
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.