Traveling salesman path problems

DOI10.1007/S10107-006-0046-8MaRDI QIDQ2476987zbMATH OpenOpenAlexFDO

Authors Fumei Lam, Alantha Newman

Publication date 12 March 2008

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

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

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

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

Recommendations

• Traveling salesman problem
• scientific article; zbMATH DE number 1947373
• scientific article; zbMATH DE number 795217
• The traveling-salesman problem
• scientific article; zbMATH DE number 6011205
• On the solution of traveling salesman problems
• Aspects of the traveling salesman problem
• The traveling salesman problem and its variations

Cites work

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

Cited in

(13)

• Travelling salesman paths on Demidenko matrices
• The traveling salesman problem in graphs with some excluded minors
• An LP-based approximation algorithm for the generalized traveling salesman path problem
• Pyramidal traveling salesman problem
• The Directed Minimum Latency Problem
• Traveling salesman problem
• A LP-based approximation algorithm for generalized traveling salesperson path problem
• Cut dominants and forbidden minors
• Directed travelling salesman problem
• Traveling salesman path problems
• scientific article; zbMATH DE number 6011205 (Why is no real title available?)
• Approximation algorithms with constant ratio for general cluster routing problems
• Approximation algorithms for general cluster routing problem

Describes a project that uses

Uses Software

• polymake

This page was built for publication: Traveling salesman path problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2476987)