Differences

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:11]
maatouk 		en:group:seminars:20110810 [2016/06/23 11:26] (current)
Line 1: Line 1:
 ---- dataentry seminar ---- ---- dataentry seminar ----
-date_dt : 2011-07-22 +date_dt : 2011-08-10 
-title : Time-space tradeoffs for randomized oblivious branching programs+title : Approximating Graphic TSP by Matchings
 speaker : Dr. Ola Svensson speaker : Dr. Ola Svensson
-affiliation : ALGO, EPFL +affiliation : ALGO - EPFL 
-time : TBA +time : 16h15 
-room : TBA+room : BC 129
 table : seminars table : seminars
 =================== ===================
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. 
 +