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érenceExternal document link
http://hal.inria.fr/inria-00494762/en/Date
2010Conference title
42èmes Journées de StatistiqueConference date
2010-05Conference city
MarseilleConference country
FranceMetadata
Show full item recordAbstract (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; ProcessusRelated items
Showing items related by title and author.
-
Monnot, Jérôme; Paschos, Vangelis; Toulouse, Sophie (2002) Communication / Conférence
-
Bellalouna, Monia; Murat, Cécile; Paschos, Vangelis (1995) Article accepté pour publication ou publié
-
Likas, Aris; Paschos, Vangelis (2002) Article accepté pour publication ou publié
-
Paschos, Vangelis; Monnot, Jérôme; Toulouse, Sophie (2003) Article accepté pour publication ou publié
-
Toulouse, Sophie; Paschos, Vangelis; Monnot, Jérôme (2003) Article accepté pour publication ou publié