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

DOI10.1016/S0377-2217(02)00222-9zbMath1012.90044OpenAlexW1994306154MaRDI QIDQ1869490

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

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

traveling salesmanapproximation algorithmNP-complete problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (5)

Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem ⋮ A 3/4 differential approximation algorithm for traveling salesman problem ⋮ A survey on the structure of approximation classes ⋮ An improved approximation algorithm for the maximum TSP ⋮ Approximation of the double traveling salesman problem with multiple stacks

Cites Work

• Approximation algorithms for indefinite quadratic programming
• Structure preserving reductions among convex optimization problems
• Toward a unified approach for the classification of NP-complete optimization problems
• Differential approximation algorithms for some combinatorial optimization problems
• On an approximation measure founded on the links between optimization and polynomial approximation theory
• The complexity of approximating a nonlinear program
• Measuring the Quality of Approximate Solutions to Zero-One Programming Problems
• The Traveling Salesman Problem with Distances One and Two
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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