The Asymmetric Travelling Salesman Problem (ATSP) is a
famous and well-studied problem in combinatorial
optimization. Consider a salesperson who wants to
visit n cities on a business trip.  The salesperson
would like to visit each of the cities exactly once
and wants to finish their trip back in their city of
origin.  Furthermore, there is a cost associated with
travelling between each pair of cities and the cost of
travelling from city A to city B may be different from
the cost of travelling from city B to city A.  The
ATSP is to find a cheapest route for our salesperson
given the above constraints.  Unfortunately, the ATSP
is an NP-complete problem and no generic
constant-bound approximation algorithm has been
developed for it.  There is a famous integer program
which is used to model the ATSP whose linear
programming relaxation gives a lower bound on the cost
of the cheapest route.  However, it is unknown if this
lower bound is always within a certain constant factor
(called the integrality gap) of the optimal value of
the integer program.  In this talk I will present the
exact integrality gap for small fixed values of n and
I will discuss some of the interesting properties of
some special solutions to the linear programming
relaxation.