1
$\begingroup$

In Le Ny et al.'s paper On the Dubins Traveling Salesman Problem (https://tinyurl.com/y59f7d8x) the authors prove, among other works, that the Dubins Traveling Salesman Problem (DTSP) is NP-hard. I will give here the basics of the proof, after which I will ask my question regarding this proof.

The authors reduce Exact Cover to DTSP, by adapting Papadimitriou's reduction from Exact Cover to Euclidean TSP (ETSP). This is done by first noting how Papadimitriou's proof makes it so Exact Cover has a solution if and only if the optimal ETSP tour has length no more than some $L$. Le Ny et al. note however that if Exact Cover admits no solution, then the optimal ETSP tour has length at least $L + \delta$, not just $L$, for some defined $\delta$. Next, they note that the optimal DTSP tour length has the following relation with an optimal ETSP tour length : $DTSP \leq ETSP + Cn$, for some $C$ (proven by Savla et al.). Le Ny et al. then go on to construct Papadimitriou's ETSP instance from a given Exact Cover instance, in which they then multiply all distances by $2Cn/\delta$. They then prove that Exact Cover has a solution if the optimal DTSP tour has length no more than $2CnL/\delta + Cn$, whereas Exact Cover has no solution if the optimal DTSP tour has length at least $2CnL/\delta + 2Cn$.

My question now is, why is it necessary to multiply all distances by $2Cn/\delta$ ? It would seem to me that not multiplying the distances by anything would still result in Exact Cover having a solution if the optimal DTSP tour has length no more than $L + Cn$, and Exact Cover having no solution if the optimal DTSP tour has length at least $L + \delta + Cn$. What am I missing here?

Improve this question
$\endgroup$
2
  • $\begingroup$ Perhaps they want integer weights? $\endgroup$
    – Yuval Filmus
    Commented Jul 13, 2019 at 14:01
  • $\begingroup$ @Yuval Filmus I don't think so, since in their other paper (citeseerx.ist.psu.edu/viewdoc/…), the authors give the same proof, but take C = 3π/2ρ, where ρ is the minimum turning radius for Dubins TSP. $\endgroup$
    – J. Schmidt
    Commented Jul 13, 2019 at 17:02

1 Answer 1

Reset to default
1
$\begingroup$

Not multiplying by $2Cn/\delta$, does not result in

... Exact Cover having no solution if the optimal DTSP tour has length at least $L+\delta+Cn$.

It in fact would result in a length at least $L+\delta$. This length is not always greater than $L+ Cn$, hence the need to multiply all distances by $2Cn/\delta$, after which one obtains the authors' result : $2CnL/\delta+2Cn$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.