# Differences

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

 en:group:seminars:20110810 [2011/07/19 16:12]maatouk en:group:seminars:20110810 [2016/06/23 11:26] (current) Both sides previous revision Previous revision 2011/07/22 14:13 maatouk 2011/07/19 16:12 maatouk 2011/07/19 16:11 maatouk 2011/07/19 16:11 maatouk 2011/07/19 16:11 maatouk 2011/07/19 16:10 maatouk created Next revision Previous revision 2011/07/22 14:13 maatouk 2011/07/19 16:12 maatouk 2011/07/19 16:11 maatouk 2011/07/19 16:11 maatouk 2011/07/19 16:11 maatouk 2011/07/19 16:10 maatouk created 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. +