On the Extended TSP Problem

Abstract

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\to 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,\dots ,|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.

17 pages