A better differential approximation ratio for symmetric TSP
From MaRDI portal
Publication:924134
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
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
