• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

Differential approximation results for the traveling salesman and related problems

Monnot, Jérôme (2002), Differential approximation results for the traveling salesman and related problems, Information Processing Letters, 82, 5, p. 229-235. http://dx.doi.org/10.1016/S0020-0190(01)00287-3

View/Open
publi115.pdf (178.6Kb)
Type
Article accepté pour publication ou publié
Date
2002
Journal name
Information Processing Letters
Volume
82
Number
5
Publisher
Elsevier
Pages
229-235
Publication identifier
http://dx.doi.org/10.1016/S0020-0190(01)00287-3
Metadata
Show full item record
Author(s)
Monnot, Jérôme cc
Abstract (EN)
This paper deals with the problem of constructing a Hamiltonian cycle of optimal weight, called TSP. We show that TSP is 2/3-differential approximable and cannot be differential approximable greater than 649/650. Next, we demonstrate that, when dealing with edge-costs 1 and 2, the same algorithm idea improves this ratio to 3/4 and we obtain a differential non-approximation threshold equal to 741/742. Remark that the 3/4-differential approximation result has been recently proved by a way more specific to the 1-, 2-case and with another algorithm in the recent conference, Symposium on Fundamentals of Computation Theory, 2001. Based upon these results, we establish new bounds for standard ratio: 5/6 for Max TSP[a,2a] and 7/8 for Max TSP[1,2]. We also derive some approximation results on partition graph problems by paths.
Subjects / Keywords
Analysis of algorithms; Performance ratio; Differential ratio; Approximation algorithms

Related items

Showing items related by title and author.

  • Thumbnail
    Differential approximation results for the traveling salesman problem with distances 1 and 2 
    Toulouse, Sophie; Paschos, Vangelis; Monnot, Jérôme (2003) Article accepté pour publication ou publié
  • Thumbnail
    Differential approximation results for the traveling salesman problem with distances 1 and 2 
    Monnot, Jérôme; Paschos, Vangelis; Toulouse, Sophie (2001) Communication / Conférence
  • Thumbnail
    Differential approximation of the traveling salesman problem 
    Monnot, Jérôme; Paschos, Vangelis; Toulouse, Sophie (2002) Communication / Conférence
  • Thumbnail
    Approximation algorithms for the traveling salesman problem 
    Paschos, Vangelis; Monnot, Jérôme; Toulouse, Sophie (2003) Article accepté pour publication ou publié
  • Thumbnail
    Labeled Traveling Salesman Problems: Complexity and approximation 
    Couëtoux, Basile; Gourvès, Laurent; Monnot, Jérôme; Telelis, Orestis (2010) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo