This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
|
en:group:seminars:20110810 [2011/07/19 16:10] maatouk created |
en:group:seminars:20110810 [2016/06/23 11:26] (current) |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | page | + | ---- dataentry seminar ---- |
| + | date_dt : 2011-08-10 | ||
| + | title : Approximating Graphic TSP by Matchings | ||
| + | speaker : Dr. Ola Svensson | ||
| + | affiliation : ALGO - EPFL | ||
| + | time : 16h15 | ||
| + | room : BC 129 | ||
| + | table : seminars | ||
| + | =================== | ||
| + | template:datatemplates:seminar | ||
| + | ----------------------- | ||
| + | |||
| + | |||
| + | ==== abstract ==== | ||
| + | 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. | ||
| + | |||