Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, May 08, 2012, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Ola Svensson (EPFL)
We will discuss a framework for approximating the metric 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.
Following this approach, there has been an exciting and rapid development for TSP on graphic metrics: our 1.461-approximation algorithm, the better analysis by Mucha'11 yielding an approximation guarantee of 1.44, and the recent development by Sevo & Vygen'12 who gave a 1.4-approximation algorithm.
Finally, we point out some interesting open problems where our techniques currently fall short from generalizing to more general metrics.
This is based on joint work with Tobias Moemke.
Automatic MiSe System Software Version 1.4803M | admin login