6.1 Consideration on the Problem Size
6.2 Recursive Algorithms
6.2.1 Master Theorem for Divide-and-Conquer
-
If \(f(n) = O(n^{\log _b(a)-\epsilon })\), then \(T(n) = \varTheta (n^{\log _b(a)})\).
-
If \(f(n) = \varTheta (n^{\log _b(a)})\), then \(T(n) = \varTheta (n^{\log _b a}\cdot \log n)\).
-
If \(f(n) = \varOmega (n^{\log _b(a)+\epsilon })\) and if a ⋅ f(n∕b) < c ⋅ f(n), with c < 1, constant, then T(n) = Θ(f(n)).
6.3 Low Complexity Constructive Methods
6.3.1 Proximity Graph Construction
6.3.2 Linearithmic Heuristic for the TSP
-
u ∈ C ∖{b, e}, the city closest to b
-
v ∈ C ∖{b, e, u}, the city closest to e
-
r − 2 other cities of C ∖{b, e, u, v} randomly picked
6.4 Local Search for Large Instances
6.4.1 Large Neighborhood Search
6.4.2 POPMUSIC
6.4.2.1 POPMUSIC for the TSP
-
The initial solution must already possess an appropriate structure; for a Euclidean problem, it should not include two intersecting edges belonging to portions of routes that are separated by a long sequence of cities, because the optimization procedure will be unable to uncross them.
-
Rather than developing an ad hoc local search like the one in Code 6.1 to optimize sub-paths, it is easier to use a general TSP solving method, for instance, Code 12.3.
-
Ultimately, we must avoid optimizing a second time a sub-path that was already optimized.