Domination analysis of some heuristics for the traveling salesman problem Original Research Article

In this paper we propose a general algorithm for the asymmetric traveling salesman problem (ATSP) on a complete digraph on n nodes which computes a tour with cost no more than a pre-specified upper bound. A special case of this algorithm is shown to have complexity O(n2) and domination number at least ∑k=0n−2 (k!). Extending this result, we show that by investing O(nk) effort, for k⩾2 and integer, it is possible to obtain a solution which is at least as good asθ=∑i=0⌊(n−2)/(k−1)⌋(n−1−i(k−1))!n−k−i(k−1)!−(n−k−1−i(k−1)))!+(z−2)!alternative tours, where z=n mod(k−1). Further, we present a patching algorithm for the ATSP and show that it has a domination number at least (n−2)!.