Approximating the multiple-depot multiple-terminal Hamiltonian path problem

DOI10.1016/J.DISOPT.2019.05.002zbMATH Open1506.90235OpenAlexW2948333404MaRDI QIDQ2010925FDOQ2010925

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

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

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)

Cites Work

• An analysis of the extended Christofides heuristic for the \(k\)-depot TSP
• \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem
• An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem
• A 3/2-approximation algorithm for the multiple TSP with a fixed number of depots
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Approximation algorithms for multiple terminal, Hamiltonian path problems
• An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem
• Improving Christofides' Algorithm for the s-t Path TSP
• An Approximation Algorithm for the Three Depots Hamiltonian Path Problem
• A 1.5-Approximation for Path TSP

Cited In (5)

• 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
• A 3/2-Approximation Algorithm for Multiple Depot Multiple Traveling Salesman 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)