An approximation algorithm for the three depots Hamiltonian path problem

DOI10.1007/978-1-4614-5134-1_25MaRDI QIDQ4596182zbMATH OpenOpenAlexFDO

Authors Mhand Hifi, Rezika Kheffache, Rachid Ouafi, A. Giannakos

Publication date 30 November 2017

Published in Optimization Theory, Decision Making, and Operations Research Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-1-4614-5134-1_25

zbMATH Keywords

approximation algorithmHamiltonian path problemtraveling salesman problem

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Recommendations

• \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem
• Approximation algorithms for the \(k\)-depots Hamiltonian path problem
• Approximation algorithms for multiple terminal, Hamiltonian path problems
• Approximating the multiple-depot multiple-terminal Hamiltonian path problem
• 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem

Cites work

• \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem
• A matroid algorithm and its application to the efficient solution of two optimization problems on graphs
• An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem
• Combinatorial optimization. Networks and matroids
• scientific article; zbMATH DE number 2143861 (Why is no real title available?)
• Matroids and a forest cover problem
• Maximum matching and a polyhedron with 0,1-vertices

Cited in

(7)

• Approximating the multiple-depot multiple-terminal Hamiltonian path problem
• Approximation algorithms for the \(k\)-depots Hamiltonian path problem
• \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem
• Approximation algorithms for multi-vehicle stacker crane problems
• A 3/2-approximation algorithm for the multiple TSP with a fixed number of depots
• Approximation algorithms for multiple terminal, Hamiltonian path problems
• 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem

This page was built for publication: An approximation algorithm for the three depots Hamiltonian path problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4596182)