Approximation algorithms for the traveling salesman problem

DOI10.1007/S001860200239MaRDI QIDQ1812290zbMATH OpenOpenAlexFDO

Authors Jérôme Monnot, Vangelis Th. Paschos, Sophie Toulouse

Publication date 23 June 2003

Published in Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s001860200239

zbMATH Keywords

approximation algorithmNP-complete problemtraveling salesman

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• scientific article; zbMATH DE number 1839451
• Differential approximation results for the traveling salesman problem with distances 1 and 2
• Differential approximation results for the traveling salesman and related problems
• scientific article; zbMATH DE number 1500530
• The Traveling Salesman Problem with Distances One and Two

Cited in

(27)

• scientific article; zbMATH DE number 1534500 (Why is no real title available?)
• Structural properties of hard metric TSP inputs (extended abstract)
• Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems
• Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem
• A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
• Combining local search and elicitation for multi-objective combinatorial optimization
• scientific article; zbMATH DE number 4095236 (Why is no real title available?)
• THE TRAVELING SALESMAN PROBLEM: APPROXIMATE ALGORITHM BY BRANCH-AND-BOUND METHOD WITH GUARANTEED PRECISION
• scientific article; zbMATH DE number 1390344 (Why is no real title available?)
• scientific article; zbMATH DE number 2080248 (Why is no real title available?)
• Differential approximation results for the traveling salesman problem with distances 1 and 2
• scientific article; zbMATH DE number 6613883 (Why is no real title available?)
• Differential approximation results for the traveling salesman and related problems
• Efficiency of a local algorithm for solving the traveling salesman problem
• Approximation Polynomial Algorithms for Some Modifications of TSP
• Generalized traveling salesman problem reduction algorithms
• A 3/4 differential approximation algorithm for traveling salesman problem
• On the approximability of the traveling salesman problem
• scientific article; zbMATH DE number 4031430 (Why is no real title available?)
• \(z\)-approximations
• A better differential approximation ratio for symmetric TSP
• A Constant Approximation Algorithm for the a priori Traveling Salesman Problem
• scientific article; zbMATH DE number 808804 (Why is no real title available?)
• Fast Algorithms for Geometric Traveling Salesman Problems
• scientific article; zbMATH DE number 598850 (Why is no real title available?)
• scientific article; zbMATH DE number 5158919 (Why is no real title available?)
• A survey on the structure of approximation classes

This page was built for publication: Approximation algorithms for the traveling salesman problem

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