4
$\begingroup$

I am an undergraduate student in Industrial Engineering. I have taken the topic of Travelling Salesman Problem as a Research Project for my final year. More specifically, I am focusing on Convex Hulls for solving the Euclidean TSP.

I have gone through the published literature and have found that there are no approximation bounds for solving TSP using this method. I have just a little background in TheoCS (Started reading for fun since the last 3 months).

My Question:

Additional Books / Papers needed for achieving a good understanding of the mathematical rigor of the problem.

Here's what I am currently going through:

  • Approximation Algorithms - Vazirani
  • Introduction to Algorithms - CLRS
  • Introduction to Graph Theory - Douglas West
  • Randomized Algorithms - Motwani and Raghavan

I have also completed an introductory online course on Algorithms by Udacity.

I think I may need some background reading in Computational Geometry (Currently I do not know more than what I read in the chapter from Cormen)

This is my first question here, so sincere apologies in case my question does not conform to the Community Standards.

EDIT:

A resource I stumbled across today: In Pursuit of the Traveling Salesman - Mathematics at the Limits of Computation. This is a good book for popular reading, providing a survey of the problem and various methods that have been used to solve it.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
5
$\begingroup$

There are a few good books on the TSP problem where you are likely to find some relevant information:

Lawler et al., eds. The traveling salesman problem: A guided tour of combinatorial optimization. Wiley, 1985.

G. Reinelt. The traveling salesman: computational solutions for TSP applications. Springer, 1994.

G. Gutin and A. P. Punnen, eds. The traveling salesman problem and its variations. Kluwer, 2004.

Good luck with your research!

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the information. I managed to access the book by Reinelt from my university library. It is a rather useful book and is in the form of lecture notes. $\endgroup$
    – rrampage
    Commented Sep 14, 2012 at 22:51
1
$\begingroup$

I have attempted concentric convex hulls to solve the TSP before, but I discovered that if a vertex happened too close to a hull, it distorts the form of the hull where it is located, so the result is not optimal. I got better results if I removed those vertices from the graph, then added them latter.

I got my best results when I started from one single convex block that was the perimeter of the entire area (covered all vertices in the map), then I proceeded to slowly reduce the radius of the block until I found the "outermost" inner vertex, then modified the "perimeter" line to connect to that vertex.

That method works as long as there are no two or more vertices at the same distance of the center. If that happens, there could be the case that the problem has multiple solutions, or you have found one of the "hard" instances of the problem.

Wish you luck!

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the feedback on convex hulls. I do not get what you are trying to convey in the 2nd para. Could you clarify? Also, is what you are doing a kind of "Onion Peeling" algorithm? $\endgroup$
    – rrampage
    Commented Sep 14, 2012 at 23:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.