Differential approximation results for the traveling salesman problem with distances 1 and 2

DOI10.1016/S0377-2217(02)00222-9MaRDI QIDQ1869490zbMATH OpenOpenAlexFDO

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

Publication date 10 April 2003

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0377-2217(02)00222-9

zbMATH Keywords

approximation algorithmNP-complete problemtraveling salesman

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 1839451
• Approximation algorithms for the traveling salesman problem
• Differential approximation results for the traveling salesman and related problems
• Fundamentals of Computation Theory
• Improved Approximation Lower Bounds for TSP with Distances One and Two

Cites work

• scientific article; zbMATH DE number 3910163 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1754594 (Why is no real title available?)
• scientific article; zbMATH DE number 3999286 (Why is no real title available?)
• scientific article; zbMATH DE number 1839451 (Why is no real title available?)
• Approximation algorithms for indefinite quadratic programming
• Differential approximation algorithms for some combinatorial optimization problems
• Measuring the Quality of Approximate Solutions to Zero-One Programming Problems
• On an approximation measure founded on the links between optimization and polynomial approximation theory
• Structure preserving reductions among convex optimization problems
• The Traveling Salesman Problem with Distances One and Two
• The complexity of approximating a nonlinear program
• Toward a unified approach for the classification of NP-complete optimization problems

Cited in

(13)

• Approximation of the double traveling salesman problem with multiple stacks
• Differential approximation results for the traveling salesman and related problems
• On the approximation hardness of dense TSP and other path problems
• An improved approximation algorithm for the maximum TSP
• New approximation algorithms for \((1,2)\)-TSP
• A better differential approximation ratio for symmetric TSP
• scientific article; zbMATH DE number 1839451 (Why is no real title available?)
• Fundamentals of Computation Theory
• A survey on the structure of approximation classes
• Approximation algorithms for the traveling salesman problem
• Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem
• A 3/4 differential approximation algorithm for traveling salesman problem
• Differential approximation of NP-hard problems with equal size feasible solutions

This page was built for publication: Differential approximation results for the traveling salesman problem with distances 1 and 2

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