\(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem

DOI10.1016/j.orl.2009.10.001zbMath1182.90074OpenAlexW1999117624MaRDI QIDQ2270326

Raja Sengupta, Sivakumar Rathinam

Publication date: 18 March 2010

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

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

zbMATH Keywords

traveling salesman problemapproximation algorithmsHamiltonian path problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (13)

Approximation algorithms for the \(k\)-depots Hamiltonian path problem ⋮ Approximation algorithms and heuristics for a 2-depot, heterogeneous Hamiltonian path problem ⋮ A primal-dual approximation algorithm for a two depot heterogeneous traveling salesman problem ⋮ An Approximation Algorithm for the Three Depots Hamiltonian Path Problem ⋮ An extension of the Christofides heuristic for a single-depot multiple Hamiltonian path problem ⋮ Approximation algorithms for multi-vehicle stacker crane problems ⋮ An analysis of the extended Christofides heuristic for the \(k\)-depot TSP ⋮ 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 ⋮ Approximation algorithms for multiple terminal, Hamiltonian path problems ⋮ 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem ⋮ Approximating the multiple-depot multiple-terminal Hamiltonian path problem ⋮ A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots

Cites Work

• Unnamed Item
• A matroid algorithm and its application to the efficient solution of two optimization problems on graphs
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Matroids and a forest cover problem
• The traveling salesman. Computational solutions for RSP applications
• On the complexity of graph tree partition problems.
• The traveling salesman problem and its variations
• An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Maximum matching and a polyhedron with 0,1-vertices

This page was built for publication: \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem