Approximation Algorithms for Asymmetric Traveling Salesperson Problems

The Traveling Salesperson Problem (TSP) is a well known and
fundamental problem in computer science with a lot of
practical applications. Since it is NP-hard (at least most of
its variants), much effort has been spent on designing good
approximation algorithms for this problem. In our talk, we will
discuss the following variants.

The first variant is the asymmetric TSP with distances one and two.
This problem is of particular interest, since despite its simplicity,
it is already APX-complete.

The second variant is the asymmetric maximum TSP. Here our goal
is to find a maximum weight (i.e., longest) Hamiltonian tour
instead of a minimum weight (i.e., shortest) Hamiltonian tour.
Algorithms for this problem frequently occur as blackboxes in
algorithms for the shortest common superstring problem. The
latter problem arises in data compression and DNA sequence assembly.

Finally, we discuss the asymmetric TSP with triangle
inequality, the most interesting variant of asymmetric
Traveling Salesperson Problems.