The TSP is a common problem in the fields of combinatorial optimization, graph theory, and operations research. Quite simply, given a
set of cities, the TSP asks for the shortest path that visits each city once and then returns to its starting point. For more information,
see William Cook's TSP Page.
Many solutions techniques for the TSP rely on linear programming;
however, when a problem with an integer valued solution, such
as the TSP, is approximated by a linear program, the fractional parts
of the approximate solution will cause some error. The
largest possible ratio of the costs of the integral true solution to
the fractional approximate solution is known as the integrality gap.
My research focuses on proving the 4/3 Conjecture for the TSP, which
states that the integrality gap of the common linear relaxation of the
problem is 4/3. My masters thesis focuses specifically on a
specific type of TSP instance known as "fractional 2-matching
instances." |
