This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
en:group:seminars:20110810 [2011/07/19 16:12]
en:group:seminars:20110810 [2016/06/23 11:26] (current)
Line 1: Line 1:
 ---- dataentry seminar ---- ---- dataentry seminar ----
 date_dt : 2011-08-10 date_dt : 2011-08-10
-title : TBA+title : Approximating Graphic TSP by Matchings
 speaker : Dr. Ola Svensson speaker : Dr. Ola Svensson
 affiliation : ALGO - EPFL affiliation : ALGO - EPFL
Line 13: Line 13:
 ==== abstract ==== ==== abstract ====
-TBA+We present a framework for approximating the metric traveling salesman problem (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 Tobias Mömke that will appear at this year's FOCS.