On the Extended TSP Problem
share
We initiate the theoretical study of Ext-TSP, a problem that originates in the area of profile-guided binary optimization. Given a graph G=(V, E) with positive edge weights w: E → R^+, and a non-increasing discount function f(·) such that f(1) = 1 and f(i) = 0 for i > k, for some parameter k that is part of the problem definition. The problem is to sequence the vertices V so as to maximize ∑_(u, v) ∈ E f(|d_u - d_v|)· w(u,v), where d_v ∈{1, …, |V| } is the position of vertex v in the sequence. We show that Ext-TSP is APX-hard to approximate in general and we give a (k+1)-approximation algorithm for general graphs and a PTAS for some sparse graph classes such as planar or treewidth-bounded graphs. Interestingly, the problem remains challenging even on very simple graph classes; indeed, there is no exact n^o(k) time algorithm for trees unless the ETH fails. We complement this negative result with an exact n^O(k) time algorithm for trees.
READ FULL TEXT