On the Extended TSP Problem

International Symposium on Algorithms and Computation (ISAAC )


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 ƒ (·) such that ƒ (1) = 1 and ƒ (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 ƒ(|du — dv |) ⋅ w (u, v ), where dv ∈ {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 no (k) time algorithm for trees unless the ETH fails. We complement this negative result with an exact nO(k) time algorithm for trees.

Latest Publications