Approximation algorithms for variants of the traveling salesman problem

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.

Name thesis:degree_name

Master of Science in Computer Science - (M.S.)

Discipline thesis:degree_discipline

Computer Science

Year

2005

Author dc:creator

• Gupta, Ankur

Contributors dc:contributor

• Artur Czumaj
• David Nassimi
• Alexandros V. Gerbessiotis

• Traveling salesman problem
• Approximation algorithms
• Computer Sciences

Repository record dc:identifier

https://digitalcommons.njit.edu/theses/496

OAI identifier oai:identifier

oai:digitalcommons.njit.edu:theses-1495