A better differential approximation ratio for symmetric TSP
type: Item
instance of: scholarly article
title: A better differential approximation ratio for symmetric TSP
zbMATH Open document ID: 1145.68051
author: Bruno Escoffier
author: Jérôme Monnot
published in: Theoretical Computer Science
publication date: 2008-05-28T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 5279824
zbMATH Keywords: approximation algorithm
zbMATH Keywords: differential ratio
zbMATH Keywords: traveling salesman problem
MaRDI profile type: Publication
full work available at URL: j.tcs.2008.01.002
OpenAlex ID: W2052608396
cites work: Structure preserving reductions among convex optimization problems
cites work: Toward a unified approach for the classification of NP-complete optimization problems
cites work: Mathematical Foundations of Computer Science 2003
cites work: Approximation algorithms for some vehicle routing problems
cites work: On the differential approximation of MIN SET COVER
cites work: Differential approximation for optimal satisfiability and related problems
cites work: Improved deterministic approximation algorithms for max TSP
cites work: Approximation results for the minimum graph coloring problem
cites work: Differential approximation algorithms for some combinatorial optimization problems
cites work: Bridging gap between standard and differential polynomial approximation: The case of bin-packing
cites work: Q3070857
cites work: On an approximation measure founded on the links between optimization and polynomial approximation theory
cites work: Q4526990
cites work: Differential approximation of MIN SAT, MAX SAT and related problems
cites work: Q4886045
cites work: Independent Sets in Bounded-Degree Hypergraphs
cites work: An extension of matching theory
cites work: \(z\)-approximations
cites work: The maximum saving partition problem
cites work: Better approximations for max TSP
cites work: A \(\frac78\)-approximation algorithm for metric Max TSP
cites work: Q4142699
cites work: Differential approximation results for the traveling salesman and related problems
cites work: Approximation algorithms for the traveling salesman problem
cites work: The Traveling Salesman Problem with Distances One and Two
cites work: Q3686457
cites work: Q3801366
cites work: Approximation algorithms for indefinite quadratic programming
DOI: 10.1016/J.TCS.2008.01.002
description: scientific article; zbMATH DE number 5279824