A Travelling Salesman variant where the next distance depends on distance travelled so far

Question

The travelling salesman problem can be seen as a problem of selecting a permutation on $\{1,\ldots,n\}$ of minimun length, where the length of a permutation $\sigma$ is determined by pairwise distances between adjacent elements, i.e., $L(\sigma) := \sum_{i=1}^n d(\sigma(i), \sigma(i-1))$, where $d$ is a function given as an input, $d: [n]\times[n]\to \mathbb{R}_+$.

I am interested in a variant in which the length of $\sigma$ is determined by the following algorithm:

1. Initialize $L := 0$;

2. For $i := 1,\ldots,n$:

   • Set $L := f(L, \sigma(i))$,

where $f: \mathbb{R}_+\times [n] \to \mathbb{R}_+$ is a function given as an input. In other words, the distance needed to reach the next node depends both on the node and on the total distance travelled so far (but not on the previous node). The computational model is Real RAM, and $f$ is given by an oracle access.

Can this variant be solved using poly($n$) calls to $f$?

EDIT: As the function $f$ represents increasing length, it should satisfy the following conditions:

• $f(L,i) > L$ for all $i, L$ (as the length of a path only increases).
• $f(L,i)$ is a weakly monotonically increasing function of $L$ for all $i$.

Sorry for the omission.

Answer 1

We answer OP's question in the negative. These results are for OP's problem with the monotonicity requirements on $f$ (added in OP's edit after @Tassle's answer, invalidating that answer).

Lemma 1. This problem:

1. has worst-case query complexity (deterministic and Las-Vegas randomized) $n 2^{n-1}$,

2. has an $O(n 2^n)$-time deterministic algorithm, and

3. is strongly NP-hard.

[Edit: strong NP-hardness depends on the encoding. See remarks at the end.]

---

Proof.

Lower bound on query complexity

Fix $n$ and let $I'$ be the instance of OP's problem defined by $$f(L, i) = L + 2^{i-1}.$$ For this instance, every permutation has the same cost, namely $\sum_{i=1}^{n} 2^{i-1} = 2^n-1$.

Let $B_b(q)$ denote the $b$th bit in the binary representation of $q\in \mathbb N$. Let $$X = \{(q, b) \in \mathbb N \times [n] : q \le 2^n-1 \textsf{ and } B_b(q) = 0\}.$$

For any $(q, b)\in X$, let $I(q,b)$ denote the instance of OP's problem defined by $$f(L, i) = \begin{cases} L + 2^{i-1} - 1& ~(L, i) = (q, b) \\ L + 2^{i-1} &~\textit{otherwise}. \end{cases}$$ Note that there is a permutation with cost $-1 + \sum_{i=1}^n 2^{i-1} = 2^n-2$, namely, take first the indices that are 1 in the binary representation of $q$, then take index $b$, then take the remaining indices.

Fix any algorithm (deterministic or randomized) that is guaranteed to give a correct answer. Simulate the algorithm on the first instance $I'$ above. If, for some $(q, b)\in X$, the algorithm doesn't query $f(q, b)$, then it can't distinguish between $I'$ and $I(q, b)$, so must give the wrong answer on one of those two instances (with positive probability). This cannot be, as the algorithm is guaranteed to give a correct answer. Hence, the algorithm must make at least $|X|$ queries.

To calculate $|X|$, associate with each $q$ the set $S(q)\subseteq [n]$ of indices of zero-bits in $q$, so $(q, b) \in X$ iff $b\in S(q)$. Then $|X| = \sum_{q=0}^{2^{n-1}} |S(q)| = \sum_{S\subseteq [n]} |S| = n 2^{n-1}$.

---

Upper bound on query complexity and run time

Consider the following dynamic-programming algorithm. For every subset $S\subseteq [n]$, define $M(S)$ to be the minimum cost of any permutation of the indices in $S$. The following recurrence holds: $$M(S) = \begin{cases} 0 & ~(S=\emptyset) \\ \min_{i\in S} f\big(M(S\setminus\{i\}), i\big) & ~(S\ne \emptyset). \end{cases}$$ The recurrence holds because of the second monotonicity requirement, that is, $L \mapsto f(L, i)$ is non-decreasing for any fixed $i$. (Because of this property, in any minimum cost permutation $(\pi_1, \pi_2, \ldots, \pi_n)$ of $[n]$, any prefix $(\pi_1, \pi_2, \ldots, \pi_k)$ can be replaced by the reordering of the prefix that gives minimum cost $M(\{\pi_1, \pi_2, \ldots, \pi_k\})$, without increasing the cost of $\pi$.)

The query complexity is $\sum_{S\subseteq [n]} |S| = n 2^{n-1}$. The running time is proportional to this.

---

Strong (?) NP-hardness

The proof, by reduction from Product Partition, is similar in spirit to @Tassle's. Given an instance $W=(w_1, w_2, \ldots, w_m)\in\mathbb N^m$ of Product Partition, let $T(W)=\sqrt{\prod_{i=1}^m w_i} \in\mathbb N$. Given $W$, the reduction constructs the instance of OP's problem, with $n=m+1$, defined by $$f(L, i) = \begin{cases} L \times w_i & ~(i \le m) \\ L & ~(i = m+1 \textsf{ and } L = T(W) \\ L + 1 & ~(i = m+1 \textsf{ and } L \ne T(W). \end{cases}$$ Suppose there is $S\subseteq [m]$ with $\prod_{i\in S} w_i = T(W)$. Then there is a solution to this instance of OP's problem that has cost $T(W)^2$. (Take any permutation of $S$, followed by $i=m+1$, followed by any permutation of $\overline S$.)

Conversely, given any permutation that achieves cost $T(W)^2$, it must be that index $m+1$ contributes nothing additional to the cost, that is, the cost $L$ just before index $m+1$ must satisfy $f(L, m+1) = L$. The only cost that does this is $L=T(W)$. So it must be that the product of the weights of the indices taken before $m+1$ is $T(W)$.

[EDIT 2: As discussed in the comments, this proof assumed $L$ is initialized to 1, but the problem specifies that $L$ is initialized to 0. To patch this, add artificial index $m+2$ with $f(0, m+2) = 1$ and $f(L, m+2) = L + T(W)^2$ for $L>0$.] $~~~\Box$

[EDIT 1: Whether this reduction shows strong NP-hardness depends on how $f$, and the target value (in decision-problem form), are encoded. Note that the value of $T(W)$ is not polynomial even when the values of the $w_i$'s are, so the standard unary encodings of $T(W)$ (in $f$) and $T(W)^2$ (in the target value) would be exponentially large. One can work around this by encoding $f$ and $T(W)^2$ differently, namely, replacing the condition $L=T(W)$ by $\prod_{i: B_i(L)=0} w_i = \prod_{i: B_i(L)=1} w_i$, and encoding $T(W)^2$ implicitly by giving the $w_i$'s in unary. In short, when defining "strongly" NP-complete for OP's problem, it's not clear how the encoding of $f$ (which is not a number) should be considered, but, it seems that there is at least a restriction of OP's problem that, with suitable encoding, is strongly NP-complete. See here for related discussion.]

---

Answer 2

Without the monotonicity condition, if $f$ is given only by oracle access, then in the worst case you need to query it $\Omega(n!)$ times.

Proof sketch:

For some sequence of integers $S=[a_1, a_2, \ldots a_k]$ (where $1\leq a_i \leq n$ for all $i$), let $E_S$ be some encoding of $S$ as a positive integer (you can easily encode $S$ with $O(k\log n)$ bits).

Fix some specific (but unknown) permutation $P = [p_1, p_2, \ldots, p_n]$ and consider the following function $f$:

• it maps $(0, x)$ to $E_{[x]}$;
• it maps $(E_{[a_1, a_2, \ldots a_k]}, x)$ to $E_{[a_1, a_2, \ldots a_k, x]}$ if $[a_1, a_2, \ldots a_k, x] \neq P$;
• it maps $(E_{[a_1, a_2, \ldots a_k]}, x)$ to $0$ if $[a_1, a_2, \ldots a_k, x] = P$;
• it maps anything else to whatever.

The length of $P$ is $0$, while the length of any other permutation is $>0$. The only way to find out $P$ is by testing it, and testing any other permutation gives you no information except that it isn't $P$. Thus, there is no better strategy than to bruteforce every permutation until finding $P$.

---

Even if $f$ is not given in a black box manner, the problem is still $\textrm{NP}$-hard.

You can show this by reducing from the partition problem. Consider an instance $S=[a_1, a_2, \ldots a_n]$, of the partition problem, with $a_1+ a_2 + \ldots + a_n = 2N$.

Let $f$ defined as follows:

• it maps $L,x$ to $L+a_x$ if $L\neq N$;
• it maps $N,x$ to $N$.

Then it is easy to see that there is a partition of $S$ into two subsets of weight $N$ if and only if the permutation with minimum weight has weight $N$.

---

EDIT: inspired by Neal Young's answer, the above reduction can be amended to satisfy the monotonicity condition. Given an instance of Partition with $m$ integers $a_1,\ldots,a_m$, define an instance of the OP problem with $n=m+1$ by:

• $f(L,i) = L+a_i$ for all $i\in \{1,\ldots,m\}$;
• $f(L,m+1) = L+2$ for $L\neq N$;
• $f(N,m+1) = N+1$.

If the Partition instance admits an equal partition, then the optimal cost is $2N+1$: the permutation starts with one subset of sum $N$, then $m+1$, then the other subset of sum $N$. If the Partition instance does not admit an equal partition, then the cost is $2N+2$ for any permutation.

Answer 3

The similarity to Travelling Salesman confused me: the more relevant problem is single-machine scheduling with non-constant job lengths. In particular, this paper surveys many scheduling problems in which the job length depends on the time in which it starts. The most relevant one seems to be this paper. In their model, the length of job $j$ is $p_j$ if it starts before some due-date $d$, and $p_j+b_j*(s_j-d)$ if it starts at time $s_j > d$. In our notation, this can be written as:

$$ f(L,i) = L + p_i \text{ if $L\leq d$} $$

$$ f(L,i) = L + p_i + b_i\cdot (L-d) \text{ if $L> d$} $$

It satisfies both conditions, and the authors prove that the problem is NP-hard.