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

DOI10.1007/s10878-023-01104-8OpenAlexW4391741341MaRDI QIDQ6123387

No author found.

Publication date: 4 March 2024

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-023-01104-8

zbMATH Keywords

approximation ratioChristofides heuristicmultiple Hamiltonian path problem

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Cites Work

• Unnamed Item
• Approximation algorithms for multiple terminal, Hamiltonian path problems
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Approximating the multiple-depot multiple-terminal 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 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
• Efficient algorithms for a family of matroid intersection problems

This page was built for publication: An extension of the Christofides heuristic for a single-depot multiple Hamiltonian path problem