SPEAKER: Mohit Singh
TIME: Thursday 4:30-5:30 pm, October 5, 2006
PLACE: PPB 300
TITLE: Improved approximation ratios for traveling salesperson tours and paths in directed graphs
ABSTRACT:
Traveling salesperson problem and its variants are one of the most widely studied combinatorial optimization problems. In this talk, we will concentrate on metric asymmetric traveling salesperson problems. In metric asymmetric traveling salesperson problems the input is a complete directed graph in which edge lengths satisfy the triangle inequality, and one is required to find a minimum length walk that visits all vertices. In ATSP the walk is required to be cyclic. In asymmetric traveling salesperson path problem (ATSPP) the walk is required to start at vertex s and to end at vertex t.
We show that the path version of the problem is almost as easy to solve as the cyclic version of the problem by showing that an \alpha-approximation for the cycle version leads to a (2+e)\alpha-approximation for the path version for every fixed e>0. We also improve on the previous best value of \alpha for the cycle version of the problem.
Joint Work with Uriel Feige.
