A better differential approximation ratio for symmetric TSP

DOI10.1016/j.tcs.2008.01.002zbMath1145.68051OpenAlexW2052608396MaRDI QIDQ924134

Bruno Escoffier, Jérôme Monnot

Publication date: 28 May 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.01.002

zbMATH Keywords

approximation algorithmtraveling salesman problemdifferential ratio

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Related Items

Differential approximation algorithm of FSMVRP ⋮ A 3/4 differential approximation algorithm for traveling salesman problem ⋮ New differential approximation algorithm for \(k\)-customer vehicle routing problem ⋮ Approximation of the double traveling salesman problem with multiple stacks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Differential approximation results for the traveling salesman and related problems
• Approximation algorithms for indefinite quadratic programming
• Differential approximation of MIN SAT, MAX SAT and related problems
• Improved deterministic approximation algorithms for max TSP
• An extension of matching theory
• 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
• Approximation results for the minimum graph coloring problem
• On an approximation measure founded on the links between optimization and polynomial approximation theory
• Better approximations for max TSP
• Approximation algorithms for some vehicle routing problems
• On the differential approximation of MIN SET COVER
• The maximum saving partition problem
• Approximation algorithms for the traveling salesman problem
• A \(\frac78\)-approximation algorithm for metric Max TSP
• Differential approximation for optimal satisfiability and related problems
• Bridging gap between standard and differential polynomial approximation: The case of bin-packing
• z-Approximations
• Independent Sets in Bounded-Degree Hypergraphs
• The Traveling Salesman Problem with Distances One and Two
• Mathematical Foundations of Computer Science 2003