Recent Progress on Graph TSP
1 : Grenoble
(G-SCOP)
Université Joseph Fourier - Grenoble I
We give an overview of some recent progress on designing approximation
algorithms for the Graph TSP problem focusing on the recent
breakthrough algorithm by Moemke and Svensson. The worst case
approximation guarantee of this algorithm was shown by Mucha to be
13/9. We then present an improved analysis of this algorithm for the
case of subquadratic graphs, i.e. graphs with maximum degree four.
| Subject : | : | typdoc_1455 |
| Language of text | : | English |
| Comment | : | This is recent work and preprint will be available at the time of the conference. |
| Topics | : | Graphs, flows, combinatorial algorithms and approximation |
| Keywords | : | TSP ; graphs ; algorithms ; linear programming |
| PDF version | : |  PDF version |
