A Permanent Approach to the Traveling Salesman Problem
Nisheeth K. Vishnoi · 2012
A randomized polynomial time algorithm is presented which, for every simple, connected, k-regular graph on n vertices, finds a tour that visits every vertex and has length at most (1 + √(64/1n k)) n with high probability. The proof follows simply from results developed in the context of permanents; Egorychev's and Falikman's theorem which lower bounds the permanent of a doubly stochastic matrix and the polynomial time algorithm of Jerrum, Sinclair and Vigoda which samples a near-random, perfect matching from a bipartite graph. The techniques in this paper suggest new permanent-based approaches for TSP which could be useful in attacking other interesting cases of TSP.