Hello - I'm attempting to find the optimal (exact) solution to the Traveling Salesman Problem in polynomial time using a Tabu search algorithm and Set theory. Currently my math skills ended with high-school calculus and some statistics in college, so the scope of analyzing mathematically the algorithm I have designed is beyond my level of knowledge (the algorithm was devised using more of a trial and error approach due to my lack of math skill).(adsbygoogle = window.adsbygoogle || []).push({});

Specifically I am in need of individual(s) who specialize in the following:

- Set Theory

- Structured Query Language

- Tuple relational calculus

- Relational algebra

- Combinatorics

I have two specific questions at this time I need help with based on my algorithm:

1. The algorithm I have outlined does not actually solve the traveling salesman problem in polynomial time, but rather is a polynomial-time approximation scheme (PTAS) or weakly polynomial run-time.

2. The algorithm I have outlined does not solve the traveling salesman problem any faster than the known current exponential time O(n^{2}2^{n})) algorithms.

3. The algorithm I have outlined does not always find the optimal (exact) solution, but rather is an approximation algorithm (Tabu search is this type of heuristic).

Note: I don't need help with #3 at this time as this is way beyond the scope of being analyzed yet. Obviously if the the #1 and #2 questions are proven to be false then #3 can be pursued.

I have a very strong assumption that one of the #1 - 3 questions will be proven to be true (hopefully for my peace of mind #1 or #2 will be proven to be true and then I don't need to pursue trying to solve this problem anymore).

Anyway to keep this short the whole point of doing all of this is to attempt a proof that P = NP.

If you can help with these questions I would be most appreciative. I would also be willing to pay/compensate you for your time or other individuals time to help me in answering the questions above as needed (within reason).

I'm not affiliated with any University or have access to professors specializing in combinatorics. In addition this is personal project (I have had a lot of free time to work on this).

I have already done all the research and documentation for the algorithm and back tested with three random data samples (2-16 point tours, and 1-18 point tour).

The pdf document can be accessed from the link:

http://jmarquart.bizland.com/TSP(Encrypted).pdf [Broken]

Password: c8fgRX239mf

This forum appears to have individuals with a very high-level of combinatorics experience that could help in analyzing this algorithm and be able to answer questions #1 and #2.

I apologize if this is not the appropriate place to post/ask this question.

Thank you very much for your time or any help you can provide!

**Physics Forums - The Fusion of Science and Community**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Attempting to find the optimal (exact) solution to TSP

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

Loading...

Similar Threads - Attempting find optimal | Date |
---|---|

A very probably flawed attempt at CH | Feb 8, 2012 |

Question on reflexivity, symmetry, and transitivity (Relation on X (Attempt inside)? | Nov 1, 2011 |

Probability of an event is p, average attempt until p happens? | Jun 11, 2011 |

Logical System+new Principles+attempt To Solve Collatz Conjecture | Feb 10, 2008 |

**Physics Forums - The Fusion of Science and Community**