Proof of bound on optimal TSP tour length in rectangular region

Question

Lemma 3 in Haimovich and Rinnooy Kan (1985) (Math of OR 10(4):527–542) says:

If $X$ [the set of nodes] is contained in a rectangle with sides $a$ and $b$, then $$ T^*(X) \le \sqrt{2(n-1)ab} + 2(a+b).$$

Here, $T^*(X)$ is the length of the optimal TSP tour through $X$, and $n=|X|$. The proof uses a clever construction that divides the rectangle into $h$ horizontal strips, builds two snaking paths along the strips, inserts every node onto both paths, and converts the paths into cycles, which are then upper bounds on $T^*(X)$. The proof winds up at the following inequality:

$$T^*(X) \le \frac32a + 2b + \frac12ah + \frac{(n-2)b}{h}.$$

I can follow the proof up to this point and I agree with it. Then they say:

The right-hand side of [the inequality above] is minimized by taking $h=\sqrt{2(n-2)b/a}$.

The proof ends there. I've confirmed that this $h$ minimizes the right-hand side of the inequality. But if we plug the optimal $h$ into the right-hand side of the inequality and we get: $$\begin{align*} T^*(X) & \le \frac{3}{2}a + 2b + \frac{a\sqrt{\frac{2(n-2)b}{a}}}{2} + \frac{(n-2)b}{\sqrt{\frac{2(n-2)b}{a}}} \\ & = \frac{3}{2}a + 2b + \sqrt{2(n-2)ab}. \end{align*}$$ I agree that this is $\le \sqrt{2(n-1)ab} + 2(a+b)$, as in the lemma—but why not state the lemma using this tighter bound? I feel like I'm missing something here.

Answer 1

As @OguzToragay has mentioned, writing $\sqrt{2(n-1)ab}$ instead of $\sqrt{2(n-2)ab}$ allows for the trivial case of one point in the Euclidean plane since $|X|\ge1$ in section 2.

The other point to make is that writing $2(a+b)$ instead of $3a/2+2b$ means that $T^*(X)$ can be succinctly expressed in terms of the perimeter of a rectangle, as in the case in Theorem 2.

Answer 2

I went over all the math included in the proof and confirmed that your claim which is: $$\frac{3a}2+2b+\sqrt{2(n-2)ab}\le\sqrt{2(n-1)ab}+2(a+b)$$

is true. But I think they didn't use the tighter bound to make the lemma more general. In the bound that you proposed the following assumption for the number of nodes must be true: $$|X|\ge 2$$ But in the suggested bound in the lemma even if $n=1$, the lemma holds.

Answer 3

The book seems to have left out a few steps. It's important to realize that

$$\frac{3}{2}a + 2b + \sqrt{2(n-2)ab}$$

is not a valid upper bound on the longest tour, even for $n\ge 2$. That can be seen by simply setting $n=2$, which reduces the above to

$$\frac{3}{2}a + 2b$$

then setting $a=6,b=1$. If we put our 2 points of $X$ into ends of a side of length $a$ of the bounding rectangle, then the one and only tour has length $2a=12$, while the above bound gives $\frac32\times 6+2\times 1 = 11$.

They key error in the argument (which I desribed in a comment before realizing it is more than a technicality) is that it proves

$$ T^*(X) \le \frac32a + 2b + \frac12ah + \frac{(n-2)b}{h}$$

only for integer values of $h$ (it is defined as a number of stripes), but then proceeds to plug in an usually non-integer value of $h$ into the right hand side of the above, which is not valid as the inequality was only proven for integer values of $h$.

As my example shows, it's more than a technicality.

I have no idea if the finally given upper bound

$$\sqrt{2(n-1)ab} + 2(a+b)$$

is also incorrect, I assume not (simply on having seemingly survived 30+ years). It also isn't countered by my previous counter example. But the above makes it clear that the step from

$$ T^*(X) \le \frac32a + 2b + \frac12ah + \frac{(n-2)b}{h}$$

to

$$ T^*(X) \le \sqrt{2(n-1)ab} + 2(a+b)$$

cannot simply be done by setting

$$h=\sqrt{2(n-2)b/a}$$

because that is not an integer usually and leads to an incorrect intermediate inequality.

Answer 4

Set \[f(h)=\frac32a+2b+\frac{ah}{2}+\frac{(n-2)b}{h}.\] Then $T^*(X)\leqslant f(h)$ for every positive integer $h$. For $n\geqslant 3$ and \begin{align*} h^* &= \sqrt{2(n-2)b/a}, & h&=\left\lceil h^*\right\rceil \end{align*} we have $h^*\leqslant h\leqslant h^*+1$, hence $$\frac{ah}{2}\leqslant\frac{a(h^*+1)}{2}=\frac{ah^*}{2}+\frac{a}{2},$$ and $$\frac{(n-2)b}{h}\leqslant\frac{(n-2)b}{h^*},$$ and then \begin{multline*} T^*(X)\leqslant f(h)=\frac32a+2b+\frac{ah}{2}+\frac{(n-2)b}{h}\\ \leqslant \frac32a+2b+\left(\frac{ah^*}{2}+\frac{a}{2}\right)+\frac{(n-2)b}{h^*} = f\left(h^*\right)+\frac{a}{2}\\ =\frac{3}{2}a+2b+\sqrt{2(n-2)ab}+\frac{a}{2} =2(a+b)+\sqrt{2(n-2)ab}. \end{multline*} The claimed inequality is trivial for $n=2$, and as mentioned in other answers, the $n-2$ is replaced by $n-1$ to cover the case $n=1$.