Domination analysis of some heuristics for the traveling salesman problem

AbstractIn 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=nmod(k−1). Further, we present a patching algorithm for the ATSP and show that it has a domination number at least (n−2)!.Since the symmetric traveling salesman problem can be formulated as an ATSP, these algorithms are applicable in this case too. However, in this case the guaranteed lower bound on the domination number would be half that of the corresponding ATSP algorithm