An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem
From MaRDI portal
Publication:2467447
DOI10.1016/J.ORL.2007.02.001zbMATH Open1169.90436OpenAlexW2016583826MaRDI QIDQ2467447FDOQ2467447
Sivakumar Rathinam, S. Darbha, W. A. Malik
Publication date: 21 January 2008
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.orl.2007.02.001
Recommendations
- A 3/2-Approximation Algorithm for Multiple Depot Multiple Traveling Salesman Problem
- 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
- 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem
- Generalized multiple depot traveling salesmen problem -- polyhedral study and exact algorithm
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Traffic problems in operations research (90B20)
Cites Work
- Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- The constrained minimum spanning tree problem
- The traveling salesman problem and its variations
- Maximizing concave functions in fixed dimension
- The traveling salesman. Computational solutions for RSP applications
- Transformation of multidepot multisalesmen problem to the standard travelling salesman problem
- Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs
- A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
- Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
- Degree-bounded minimum spanning trees
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Technical Note—A Note on the Symmetric Multiple Traveling Salesman Problem with Fixed Charges
- Technical Note—A Note on the Multiple Traveling Salesmen Problem
Cited In (26)
- A 3/2-approximation algorithm for the multiple TSP with a fixed number of depots
- A 3/2-approximation algorithm for the multiple Hamiltonian path problem with no prefixed endpoints
- Approximation algorithms and heuristics for a 2-depot, heterogeneous Hamiltonian path problem
- An analysis of the extended Christofides heuristic for the \(k\)-depot TSP
- Approximation algorithms for multiple terminal, Hamiltonian path problems
- A 3/2-Approximation Algorithm for Multiple Depot Multiple Traveling Salesman Problem
- An approximation algorithm for vehicle routing with compatibility constraints
- A hyper-heuristic based artificial bee colony algorithm for \(k\)-interconnected multi-depot multi-traveling salesman problem
- Approximating the multiple-depot multiple-terminal Hamiltonian path problem
- Approximation algorithms for the \(k\)-depots Hamiltonian path problem
- Technical Note—An Improved Transformation of the Symmetric Multiple Traveling Salesman Problem
- A primal-dual approximation algorithm for a two depot heterogeneous traveling salesman problem
- An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem
- A Lagrangian-Based Algorithm for a Combinatorial Motion Planning Problem
- Improved algorithms for joint optimization of facility locations and network connections
- The \(m\)-Steiner traveling salesman problem with online edge blockages
- 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem
- New approximation algorithms for the heterogeneous weighted delivery problem
- New approximation algorithms for the heterogeneous weighted delivery problem
- An asymptotically tight online algorithm for \(m\)-steiner traveling salesman problem
- An Approximation Algorithm for the Three Depots Hamiltonian Path Problem
- Generalized multiple depot traveling salesmen problem -- polyhedral study and exact algorithm
- Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees
- Multi-depot multiple TSP: a polyhedral study and computational results
- \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem
- An extension of the Christofides heuristic for a single-depot multiple Hamiltonian path problem
Uses Software
This page was built for publication: An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2467447)
