Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Approximating Graphic TSP by Matchings
du groupe Algorithmique Distribuée

Date 2011-07-18  14:00-15:00
TitreApproximating Graphic TSP by Matchings  
RésuméWe present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges in order to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a decreased cost. For the TSP on graphic metrics (graph-TSP), the approach yields a 1.461-approximation algorithm with respect to the Held-Karp lower bound. For graph-TSP restricted to a class of graphs that contains degree three bounded and claw-free graphs, we show that the integrality gap of the Held-Karp relaxation matches the conjectured ratio 4/3. The framework allows for generalizations in a natural way and also leads to a 1.586-approximation algorithm for the traveling salesman path problem on graphic metrics where the start and end vertices are prespecified. This is joint work with Ola Svensson.  
Lieus. 178 
OrateurTobias Moemke 
Emailmoemke@nada.kth.se 
UrlKTH Stockholm 



Aucun document lié à cet événement.

Retour
Retour à l'index