Research

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} ƒ(|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.