  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 \rightarrow R^+$, and a non-increasing discount
function $f(\cdot)$ 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 $\sum_{(u, v) \in E} f(|d_u -
d_v|)\cdot w(u,v)$, where $d_v \in \{1, \ldots, |V| \}$ is the position of
vertex~$v$ in the sequence.
  We show that \prob{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.
