Approximating the multiple-depot multiple-terminal Hamiltonian path problem

DOI10.1016/J.DISOPT.2019.05.002MaRDI QIDQ2010925zbMATH OpenOpenAlexFDO

Authors Zhaohui Liu, Yi-Chen Yang

Publication date 28 November 2019

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2019.05.002

zbMATH Keywords

approximation algorithmmatroidHamiltonian path problemconstrained forest

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Recommendations

• Approximation algorithms for multiple terminal, Hamiltonian path problems
• Approximation algorithms for the \(k\)-depots Hamiltonian path 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
• \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem

Cites work

• A 1.5-approximation for path TSP
• 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
• Improving Christofides' algorithm for the \(s\)-\(t\) path TSP
• \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem

Cited in

(8)

• 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 for multiple terminal, Hamiltonian path problems
• A 3/2-Approximation Algorithm for Multiple Depot Multiple Traveling Salesman Problem
• An approximation algorithm for the three depots 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
• An extension of the Christofides heuristic for a single-depot multiple Hamiltonian path problem

This page was built for publication: Approximating the multiple-depot multiple-terminal Hamiltonian path problem

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