# Computational Complexity of Solutions of the Traveling Purchaser Problem on a Small Data Set

I have encountered a problem that is essentially the textbook statement of the Traveling Purchaser Problem. I don't know if this is the proper place to put this, if not then I will delete it.

Also a note is that while I have done some studying on my own of computer science, I did not have much formal education in it. I do have a reasonably strong math background though.

Now on to the background of the problem:

I know the Traveling Purchaser Problem is NP-Hard, and thus there is no optimal solution algorithm known. I know that as such, there are many different solution algorithms, of varying efficiency. The (admittedly few) papers that I have seen though use this on sets of 100s of nodes, and don't explicitly state the complexity of the algorithm in terms of big-O notation or similar functions. Since my data set is relatively small (7 nodes and about 50 items to purchase). I was wondering if it might be a waste of time to implement a complex, if efficient, algorithm. But that is not my question, as I think such questions would be out of place here, it is just the background.

My question is the following:

What are some of the common algorithms for approximating the solution to the Traveling Purchaser Problem along with their computational complexity in terms of the number of nodes and the number of items to purchase.

• For 7 nodes, there are only 7! = 5040 possible full orders. I'm confident that just enumerating all of them with a tree search, keeping track of the cheapest price so far for each good that you need in the current partial solution, will solve this problem in under 1ms. – j_random_hacker May 15 '18 at 12:52