CODEWITHSUNDEEP
time-complexitytraveling-salesmanexponentialdivide-and-conquer
MTA
MTA

Reputation: 809

Time complexity of TSP

Basically I'm not sure how to measure time complexity.

I know that TSP is an NP-hard problem, that means that the time complexity of an algorithm used to solve it is exponential: O(2^n)

What if I divide into sub-problems and solve the subproblems them combine them to form a complete solution? The time complexity is less right? Maybe something like:

O(n) = 1 if n = 1 O(n) = a (n/b) + cn

A problem of size n is divided into a subproblems of size n/b, here cn is linear time complexity.

Ref: http://devernay.free.fr/cours/algo/docs/10%20-%20Time%20Complexity.pdf

So does that mean time complexity is O(n log n) if you have a divide an conquer approach? I feel like there is something wrong with this logic. It cant be possible to reduce exponential time complexity to n log n through a divide and conquer approach.

What is the time complexity of: 1 - Solving TSP => exponential O(2^n), right? 2 - First dividing TSP into subproblems, then solving subproblems using the same approach used in 1? Surely less than exponential?

Sorry I'm a little confused, any help is appreciated.

Upvotes: 0

Views: 1379

Answers (1)

MR Carbonell
MR Carbonell

Reputation: 1

This is done for very large TSP. For example, galactic TSP with 1,691,937,135 nodes

https://www.cs.columbia.edu/~idrori/galaxytsp.pdf

Uses quadtree decomposition, solve and merge subtours. From the pdf:

Algorithm 1 Approximate and Merge Tiles
Input: Tiles T = (T1, T2, T3, T4)
Output: Merged super-tile ST
Compute LKH(T1), LKH(T2), LKH(T3), LKH(T4)
Compute tile centroids (μ1, μ2, μ3, μ4)
Let current shortest tour ST = LKH(T1)
for t = 2, 3, 4 do
Find m nearest neighbors in ST to μt: Nm∈ST (μt) and let these be join points.
for each ni ∈ Nm(μt) do
Find k nearest neighbors in tile Tt to ni: Nk∈Tt (ni)and let these be tile tour entry points.
for each nj ∈ Nk (ni) do
Let na be node after ni in ST
Let nb be node before nj in LKH(Tt)
Remove edges ni → na and nb → nj
Add edges ni → nj and nb → na
Compute new merged tour and length and store
end for
end for
ST = Shortest tour found, up to tile Tt
end for
return Merged tile solution ST

Upvotes: 0

Related Questions