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

> Recherche > Optimisation combinatoire

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 cet article Facebook Twitter Linked In
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

 


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 cet article Facebook Twitter Linked In

mise à jour le 31 mars 2015

Université Grenoble Alpes