Approximating the multiple-depot multiple-terminal Hamiltonian path problem

DOI10.1016/j.disopt.2019.05.002zbMath1506.90235OpenAlexW2948333404MaRDI QIDQ2010925

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)

Related Items (1)

An extension of the Christofides heuristic for a single-depot multiple Hamiltonian path problem

Cites Work

• An analysis of the extended Christofides heuristic for the \(k\)-depot TSP
• Approximation algorithms for multiple terminal, Hamiltonian path problems
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• 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
• 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
• 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

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