Accuracy and problem time analysis for solving the traveling salesman problem with the "anti-greedy" algorithm

In this paper a new "anti-greedy" algorithm for the traveling salesman problem is considered. The idea of the "anti-greedy" algorithm consists in consequent elimination of the longest edges from a graph according to two rules: each node of the graph should have at least two incident edges; the graph should not have cycles with less than n edges. This algorithm finds more accurate solutions in comparison with well-known polynomial algorithms, especially for non-Euclidean graphs.