• 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 - No thumbnail

Well solved cases of probabilistic traveling salesman problem

Bellalouna, Monia; Paschos, Vangelis; Khaznaji, Walid (2010), Well solved cases of probabilistic traveling salesman problem, 42èmes Journées de Statistique, 2010-05, Marseille, France

Type
Communication / Conférence
External document link
http://hal.inria.fr/inria-00494762/en/
Date
2010
Conference title
42èmes Journées de Statistique
Conference date
2010-05
Conference city
Marseille
Conference country
France
Metadata
Show full item record
Author(s)
Bellalouna, Monia
Paschos, Vangelis
Khaznaji, Walid
Abstract (FR)
Le problème du voyageur de commerce est généralement NP-Hard. Notre but est de chercher des cas qui sont "Faciles", c'est à dire résolubles en temps polynomial. Le Problème du Voyageur de Commerce Petit illustre bien ces cas, notre étude comporte deux volets, d'abord nous donnons la relation entre le problème déterministe et son homologue probabiliste, ensuite nous montrons un résultat remarquable, à savoir : ce problème est stable : la perturbation par l'absence de certaines données n'influe pas l'optimalité de la solution.
Abstract (EN)
The Probabilistic Traveling Salesman Problem is in general NP-Hard, the objective of this paper is to look for particular cases which can be solved in an easy way. First we give the relation between the two problems deterministic and probabilistic. Second, we study the stability of the deterministic problem. We prove that in the small traveling salesman problem, several tours were optimal, but there is only one stable among them : The absence of certain cities does not disturb the tour induced by the method of modi cation of the optimal tour a priori.
Subjects / Keywords
Voyageur de commerce; Statistiques mathématiques; Processus

Related items

Showing items related by title and author.

  • Thumbnail
    Differential approximation of the traveling salesman problem 
    Monnot, Jérôme; Paschos, Vangelis; Toulouse, Sophie (2002) Communication / Conférence
  • Thumbnail
    Probabilistic combinatorial optimization problems: a new domain in Operational Research 
    Bellalouna, Monia; Murat, Cécile; Paschos, Vangelis (1995) Article accepté pour publication ou publié
  • Thumbnail
    A note on a new greedy-solution representation and a new greedy parallelizable heuristic for the traveling salesman problem 
    Likas, Aris; Paschos, Vangelis (2002) Article accepté pour publication ou publié
  • Thumbnail
    Approximation algorithms for the traveling salesman problem 
    Paschos, Vangelis; Monnot, Jérôme; Toulouse, Sophie (2003) Article accepté pour publication ou publié
  • 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é
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