Traveling salesman path problems

DOI10.1007/s10107-006-0046-8zbMath1135.90039OpenAlexW1976231547MaRDI QIDQ2476987

Alantha Newman, Fumei Lam

Publication date: 12 March 2008

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-006-0046-8

zbMATH Keywords

approximation algorithmperfect graphstraveling salesman walk problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)

Related Items (8)

A LP-based approximation algorithm for generalized traveling salesperson path problem ⋮ An Improved Integrality Gap for Asymmetric TSP Paths ⋮ An LP-based approximation algorithm for the generalized traveling salesman path problem ⋮ The Directed Minimum Latency Problem ⋮ Traveling salesman path problems ⋮ Approximation algorithms for general cluster routing problem ⋮ Cut Dominants and Forbidden Minors ⋮ Approximation algorithms with constant ratio for general cluster routing problems

Uses Software

• polymake

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A cutting plane procedure for the travelling salesman problem on road networks
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities
• The traveling salesman problem in graphs with some excluded minors
• A \(\frac{5}{3}\)-approximation algorithm for the clusterd traveling salesman tour and path problems
• The Steiner tree polytope and related polyhedra
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• The traveling salesman problem and its variations
• The graphical relaxation: A new framework for the symmetric traveling salesman polytope
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Traveling salesman path problems
• The traveling salesman problem on a graph and some related integer polyhedra
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem

This page was built for publication: Traveling salesman path problems