The traveling salesman problem: New polynomial approximation algorithms and domination analysis

For the traveling salesman problem (TSP) on n nodes, we show that a tour which is better than Ω((n/2)!) alternative tours can be identified on O(n³) time. Also we provide another algorithm of complexity O(n³) which is guaranteed to produce a solution which is better than Ω((n/(k + 1))!(k!)^n/(k+1)) alternative tours, whenever k is fixed. Further we show that by using an O(n⁴) algorithm, a TSP tour which dominates Ω((n/2)!n) alternative tours can be identified. We also suggest an O(n⁵) algorithm with improved domination number.