Approximation algorithms for multiple terminal, Hamiltonian path problems

DOI10.1007/s11590-010-0252-4zbMath1259.90106arXiv1111.0567MaRDI 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 problem; approximation algorithms; Hamiltonian path problem

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

Related Items

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