This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
en:group:seminars:20110810 [2011/07/19 16:12] maatouk |
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. | ||
| + | |||