Approximation algorithms for the \(k\)-depots Hamiltonian path problem

DOI10.1007/s11590-021-01774-5zbMath1491.90143OpenAlexW3174352199WikidataQ114222158 ScholiaQ114222158MaRDI QIDQ2128771

Wei Yu, Zhaohui Liu, 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 algorithmHamiltonian path problemmultiple depotsChristofides-like heuristicmultiple salesmen

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

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

Cites Work

• Unnamed Item
• 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
• An Approximation Algorithm for the Three Depots Hamiltonian Path Problem
• Combinatorial optimization. Theory and algorithms