Tuesday, 15:45 - 16:10 h, Room: H 3010

 

Tobias Mömke
Approximationg graphic TSP by matchings

Coauthor: Ola Svensson

 

Abstract:
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.

 

Talk 2 of the invited session Tue.3.H 3010
"Travelling salesman problem II" [...]
Cluster 1
"Approximation & online algorithms" [...]

 

  To apply for Payday Loans In United States you don't have to seek the help of relatives or go to a bank. They were lucky to produce Viagra Sublingual which dissolves under the tongue and penetrates into the blood causing erection faster than any other drugs.