Question 34: Recall the Traveling Salesman Problem: Definition Travel…

Recall the Traveling Salesman Problem:

Definition

Traveling Salesman Problem

Input: A set of distinct cities $\{c_1, c_2, \ldots, c_n\}$ and for each pair $c_i \neq c_j$ the distance between $c_i$ and $c_j$, denoted by $d(c_i, c_j)$, and a budget $k$.

Question: Determine if there is a permutation $\pi$ of $\{1, 2, \ldots, n\}$, such that the following sum:

$\sum_{i=1}^{n-1} d\left(c_{\pi(i)}, c_{\pi(i+1)}\right) + d\left(c_{\pi(n)}, c_{\pi(1)}\right)$

is at most $k$.

The dynamic programming algorithm for TSP computes for every pair $(S, c_i)$, where $S$ is a nonempty subset of $\{c_2, c_3, \ldots, c_n\}$ and $c_i \in S$, the value $OPT[S, c_i]$ which is the minimum length of a tour which starts in $c_1$, visits all cities from $S$ and ends in $c_i$. We compute the values $OPT[S, c_i]$ in order of increasing cardinality of $S$. The computation of $OPT[S, c_i]$ in the case $S$ contains only one city is trivial, because in this case, $OPT[S, c_i] = d(c_1, c_i)$. For the case $|S| > 1$, observe that if in some optimal tour in $S$ terminating in $c_i$, the city $c_j$ immediately precedes $c_i$, then

$OPT[S, c_i] = OPT[S \setminus \{c_i\}, c_j] + d(c_j, c_i).$

This leads us to expressing the value of $OPT[S, c_i]$ in terms of subsets of $S$ as follows.

$OPT[S, c_i] = \min\{OPT[S \setminus \{c_i\}, c_j] + \star : c_j \in S \setminus \{c_i\}\}.$

Note that the minimum is taken over $c_j \in S \setminus \{c_i\}$. What is the missing term?