Approximation algorithms for the k-depots Hamiltonian path problem

DOI10.1007/S11590-021-01774-5MaRDI QIDQ2128771zbMATH OpenOpenAlexWikidataFDO

Authors Zhaohui Liu, Wei Yu, Yi-Chen Yang

Publication date 22 April 2022

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-021-01774-5

zbMATH Keywords

approximation algorithmChristofides-like heuristicHamiltonian path problemmultiple depotsmultiple salesmen

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Approximating the multiple-depot multiple-terminal Hamiltonian path problem
• Approximation algorithms for multiple terminal, Hamiltonian path problems
• An approximation algorithm for the three depots Hamiltonian path problem
• \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem
• An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem

Cites work

• \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem
• A 3/2-approximation algorithm for the multiple TSP with a fixed number of depots
• An analysis of the extended Christofides heuristic for the \(k\)-depot TSP
• An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem
• An approximation algorithm for the three depots Hamiltonian path problem
• An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Approximation algorithms for multiple terminal, Hamiltonian path problems
• Combinatorial optimization. Theory and algorithms
• scientific article; zbMATH DE number 1102774 (Why is no real title available?)

Cited in

(10)

• An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem
• Approximating the multiple-depot multiple-terminal Hamiltonian path problem
• \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem
• Approximation algorithms and heuristics for a 2-depot, heterogeneous Hamiltonian path 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
• An analysis of the extended Christofides heuristic for the \(k\)-depot TSP
• A 3/2-approximation algorithm for the multiple Hamiltonian path problem with no prefixed endpoints
• Approximating split delivery path routing problems
• Approximation algorithms for multiple terminal, Hamiltonian path problems

This page was built for publication: Approximation algorithms for the \(k\)-depots Hamiltonian path problem

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