Aller au menu Aller au contenu
Optimisation Combinatoire
Laboratoire des Sciences pour la Conception, l'Optimisation et la Production de Grenoble
Optimisation Combinatoire
Optimisation Combinatoire
< >

> GSCOP_Recherche > GSCOP_OptimisationCombinatoire

Séminaire de Mathématiques Discrètes jeudi 26 mars à 14h30 - Jens Vygen

Publié le 20 mars 2015
A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail Partagez cet article Facebook Twitter Linked In Google+ Viadeo
Colloque / Séminaire 26 mars 2015

Le jeudi 26 mars à 14h30, en salle C319, nous aurons le plaisir d'écouter Jens Vygen (Université de Bonn). Reassembling Trees for the Traveling Salesman

vignette-seminaireOC.jpg

vignette-seminaireOC.jpg

 


Reassembling Trees for the Traveling Salesman




Many recent approximation algorithms for different variants of the traveling salesman problem (asymmetric TSP, graph TSP, s-t-path TSP) exploit the well-known fact that a solution of the natural linear programming relaxation can be written as convex combination of spanning trees. The main argument then is that randomly sampling a tree from such a distribution and then completing the tree to a tour at minimum cost yields a better approximation guarantee than simply taking a minimum cost spanning tree (as in Christofides' algorithm). We argue that an additional step can help: reassembling the spanning trees before sampling. Exchanging two edges in a pair of spanning trees can improve their properties under certain conditions. We demonstrate the usefulness for the metric s-t-path TSP by devising a deterministic polynomial-time algorithm that improves on Sebo's previously best approximation ratio of 8/5.

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail Partagez cet article Facebook Twitter Linked In Google+ Viadeo

mise à jour le 31 mars 2015

  • Tutelle CNRS
  • Tutelle Grenoble INP
  • Université Joseph Fourier
  • Tutelle UMR
Univ. Grenoble Alpes