An analysis of the extended Christofides heuristic for the k-depot TSP
From MaRDI portal
Publication:635520
DOI10.1016/J.ORL.2011.03.002zbMATH Open1219.90149OpenAlexW2056897184MaRDI QIDQ635520FDOQ635520
Authors: Zhou Xu, Liang Xu, Brian Rodrigues 
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
Recommendations
- An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem
- A 3/2-approximation algorithm for the multiple TSP with a fixed number of depots
- A 3/2-Approximation Algorithm for Multiple Depot Multiple Traveling Salesman Problem
- Approximation algorithms for the \(k\)-depots Hamiltonian path problem
- 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem
Cites Work
- Title not available (Why is that?)
- An Analysis of Several Heuristics for the Traveling Salesman Problem
- Combinatorial optimization. Theory and algorithms.
- A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem
- Arc Routing Problems, Part I: The Chinese Postman 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
- 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
- New assignment algorithms for the multi-depot vehicle routing problem
- Approximations for minimum and min-max vehicle routing problems
Cited In (12)
- A 3/2-approximation algorithm for the multiple TSP with a fixed number of depots
- A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms
- Approximation algorithms for multi-vehicle stacker crane problems
- Approximating the multiple-depot multiple-terminal Hamiltonian path problem
- Improved approximation algorithms for multidepot capacitated vehicle routing
- Approximation algorithms for the \(k\)-depots Hamiltonian path problem
- An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem
- The \(m\)-Steiner traveling salesman problem with online edge blockages
- Exact and heuristic algorithms for routing AGV on path with precedence constraints
- An asymptotically tight online algorithm for \(m\)-steiner traveling salesman problem
- 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 a single-depot multiple Hamiltonian path problem
This page was built for publication: An analysis of the extended Christofides heuristic for the \(k\)-depot TSP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q635520)
