Priority functions for the approximation of the metric TSP

• We present (to the best of our knowledge) the first implicit approximation algorithm for an NP-hard graph problem, the metric TSP.
• It is based on the well-known double minimum spanning tree heuristic but the shortcuts are computed in a new way using priority functions.
• The implicit approximations algorithm needs only a polylogarithmic number of functional operations with respect to the number of vertices of the input graph.
• Experimental results have been performed to analyze the approximation error.

One approach to deal with very large graphs G=(V,E)G=(V,E) consists of a Boolean encoding of the vertices and edges and implicitly representing and manipulating the characteristic functions of V and E using OBDDs, a well-known data structure for Boolean functions. A possibility to attack hard optimization problems is the design of approximation algorithms. Based on the well-known double minimum spanning tree heuristic, the first implicit approximation algorithm is designed for an NP-hard problem, the metric traveling salesperson problem. Priority functions are used in a new approach for the computation of the shortcuts and three different variants are experimentally evaluated with respect to the approximation quality. Furthermore, the worst case complexity of the approximation algorithm is investigated in more detail.