The New Jersey Institute of Technology's
Electronic Theses & Dissertations Project

Title:	Approximation algorithms for variants of the traveling salesman problem
Author:	Gupta, Ankur
View Online:	njit-etd2005-105 (x, 42 pages ~ 2.2 MB pdf)
Department:	Department of Computer Science
Degree:	Master of Science
Program:	Computer Science
Document Type:	Thesis
Advisory Committee:	Czumaj, Artur (Committee chair) Nassimi, David (Committee member) Gerbessiotis, Alexandros V. (Committee member)
Date:	2005-05
Keywords:	Traveling salesman problem Approximation algorithms
Availability:	Unrestricted
Abstract:	The traveling salesman problem, hereafter abbreviated and referred to as TSP, is a very well known NP-optimization problem and is one of the most widely researched problems in computer science. Classical TSP is one of the original NP - hard problems [1]. It is also known to be NP - hard to approximate within any factor and thus there is no approximation algorithm for TSP for general graphs, unless P = NP. However, given the added constraint that edges of the graph observe triangle inequality, it has been shown that it is possible achieve a good approximation to the optimal solution [2]. TSP has a number of variants that have been deeply researched over the years. Approximations of varying degrees have been achieved depending on the complexity presented by the problem setup. An obvious variant is that of finding a maximum weight hamiltonian tour, also informally known as the "taxicab ripoff problem". The problem is not equivalent to the minimization problem when the edge weights are non-negative and does allow good approximations. Also important is the problem when the graph is not symmetric. The problem in this case, as should be expected, is slightly tougher to approximate. Another very well researched problem is when weights of edges are drawn from the set { 1, 2}. This study was focused on gaining an understanding of these algorithms keeping in mind the primary endeavor of improving them. This thesis presents approximation algorithms for the aforementioned and other variants of the TSP, and is focused on the techniques and methods used for developing these algorithms.