On the approximability of the traveling salesman problem (Q2495698)

In the paper the previously known inapproximability bounds for symmetric as well as asymmetric traveling salesman problems are improved by more than an order of magnitude. First, a new inapproximability bound for the asymmetric traveling salesman problem is given by providing a special reduction from maximum satisfiability of linear equations modulo 2 with three variables per equation. The reduction relies on a probabilistic construction of a graph with specialized properties, the so-called \(b\)-pusher, and is essentially nonconstructive. The same basic ideas (with a new set of gadgets) are then used to prove a new inapproximability bound for the symmetric traveling salesman problem.