Better differential approximation for symmetric TSP

In this paper, we study the approximability properties of symmetric TSP under an approximation measure called the differential ratio. More precisely, we improve up to 3/4 − ε (for any ε > 0) the best differential ratio of 2/3 known so far, given in Hassin and Khuller, "z-Approximations", J. of Algorithms, 41(2), 429-442, 2001.

Data and Resources

Additional Info

Field Value
Source https://hal.science/hal-00917811
Author Escoffier, Bruno, Monnot, Jérôme
Maintainer CCSD
Last Updated May 7, 2026, 20:11 (UTC)
Created May 7, 2026, 20:11 (UTC)
Identifier hal-00917811
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE) ; Université Paris Dauphine-PSL ; Université Paris Sciences et Lettres (PSL)-Université Paris Sciences et Lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)
creator Escoffier, Bruno
date 2007-07-03T00:00:00
harvest_object_id 7b36706e-af27-488b-9594-c96b8cf99dcd
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-06-13T00:00:00
set_spec type:UNDEFINED