Thursday 27
Graphs, flows, combinatorial algorithms and approximation
Vincent Chau
› 10:30 - 11:00 (30min)
› Bât B - TD 43
Recent Progress on Graph TSP
Alantha Newman  1@  
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.


Online user: 1