Two Algorithmic Results for the Traveling Salesman Problem

For any norm in a Euclidean space and for any number δ > 0 we present a polynomial time algorithm which computes a Hamiltonian circuit with the given vertices in the space whose length approximates, with relative error less than δ, the largest length of a Hamiltonian circuit with these vertices. We also present an algorithm which for a given graph with n vertices computes the number of Hamiltonian circuits in this graph with 2^{n+O(log n)} time complexity and a polynomial in n space complexity. As a by-product of our approach we prove that the permanent of a matrix can be computed in polynomial time provided the rank of the matrix is fixed.