On the approximability of the traveling salesman problem (Q2495698): Difference between revisions

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.