University of Ottawa - Carleton University
Ottawa-Carleton Institute for Computer Science (OCICS) Presentation
|
March 1, 2013 @ 10:00a.m.
Approximation Methods for Graph TSP
|
Speaker: Fu Yao
Location: CBY A707 (Colonel By building) |
ABSTRACT
The Travelling Salesman problem (TSP) is a famous problem in combinatorial optimization. It basically involves finding a shortest tour in a collection of cities with weights representing the distance between each pair of cities. It has many applications in industry, such as the scheduling of a machine to drill holes in a circuit board or other object. For most of these applications the weights are metric, meaning they satisfy the triangle inequality. As the TSP is known to be NP-hard even in the metric case, it is considered highly unlikely that we will ever find an efficient method for solving it. So we seek approximation methods, which are efficient methods which come with a performance guarantee. For metric TSP, Christofidesâ 3/2-approximation algorithm is still the best method since 1976, with no improvement in over 35 years. However recently there have been many exciting results for graph TSP, like Sebo and Vygenâs 7/5-approximation. We are now focusing on new approximation methods for graph TSP. |
| Return to Schedule |
|
