Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I am interested if there exists a following version of the travelling salesman problem:

INSTANCE: A finite set $C = \{1,2,\dots,k\}$ of cities, a positive integer distance $\delta(i,j)$ for each pair of cities, and two positive integers $d$ and $B$.

QUESTION: Is there a tour that visits every city in $C$, includes exactly $d$ detours, and has total length no more then $B$? In other words, suppose $OPT$ is the optimal permutation of the cities; that is, $OPT(i)$ is the next city after city $i$ in an optimal traveling salesman tour. Is there an ordering $x(0), \dots, x(k-1)$ of the cities such that $$\sum_{i=1}^{k} \delta(x(i), x((i+1) \bmod k)) \leq B$$ and there are exactly $d$ indices $i$ where $x((i+1) \bmod k) \ne OPT(x(i))$?

The $d$ implies that if my shortest tour is $a\rightarrow b \rightarrow c\rightarrow a$ but $d=1$ then what would be the shortest path if I had to first go to $c$, $ a \rightarrow c \rightarrow ...$. So $d$ tells me that I have to make $d$ number of wrong choices but I can choose these choices in any way I want to to minimize the length of the path.

Is this a problem worthwhile describing? Or if it has been described where could I see an example?

share|improve this question
1  
You define it, it exists. However, I wonder why the formal definition of your question does not relate to $d$ at all. –  Raphael Feb 15 '13 at 11:04
3  
I revised the formal statement to incorporate $d$, but please verify that I haven't changed the intent of the question. A major issue with this formulation is that the optimal TSO tour is not unique; the reversal of any optimal TSP tour is another optimal TSP tour. –  JeffE Feb 15 '13 at 16:55
    
Maybe you can circumvent the issue raised by JeffE by asking for a tour which differs in exactly $d$ places from some optimal tour $OPT$. In other words, there is atleast one optimal tour, from which the desired tour differs in $d$ places. –  Paresh Feb 15 '13 at 16:59
2  
What would be an application of or a motivation for this problem? –  Yuval Filmus Feb 18 '13 at 5:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.