Approximation algorithms for multiple terminal, Hamiltonian path problems

DOI10.1007/s11590-010-0252-4zbMath1259.90106arXiv1111.0567OpenAlexW2077326088MaRDI QIDQ691412

Sivakumar Rathinam, Jungyun Bae

Publication date: 30 November 2012

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1111.0567

zbMATH Keywords

traveling salesman problemapproximation algorithmsHamiltonian path problem

Mathematics Subject Classification ID

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

Related Items

Approximation algorithms for the \(k\)-depots Hamiltonian path problem ⋮ An extension of the Christofides heuristic for a single-depot multiple Hamiltonian path problem ⋮ Approximating the multiple-depot multiple-terminal Hamiltonian path problem ⋮ A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A matroid algorithm and its application to the efficient solution of two optimization problems on graphs
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Matroids and a forest cover problem
• Approximation and complexity in numerical optimization. Continuous and discrete problems. Conference, Univ. of Florida, Orlando, FL, USA, February 28 - March 2, 1999
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• The traveling salesman problem and its variations
• An extension of Christofides heuristic to the k-person travelling salesman 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
• On two geometric problems related to the travelling salesman problem
• A 3/2-Approximation Algorithm for Multiple Depot Multiple Traveling Salesman Problem
• Maximum matching and a polyhedron with 0,1-vertices

This page was built for publication: Approximation algorithms for multiple terminal, Hamiltonian path problems