11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm concerend about the definition of $h$ as the number of stripes, which would make it a positive integer. The value of $h$ that is found as minimizer is certainly not an integer most of the time, so that makes the derivation incorrect. The book can't take an inequality that has been proven for integer $h$ only and then plug in a (usually) non-integer value! $\endgroup$ – Ingix Sep 29 at 2:43
  • $\begingroup$ @Ingix But it's good enough to give bounds. Think about it like this: Let $R(h)$ be the right-hand side of the first inequality above for given $h$, i.e., $R(h) = 3a/2 + 2b + ...$. Then $T^*(X) \le R(h)$ for any $h$, so $T^*(X) \le R(h^*)$ (where $h^*$ is the minimizer), and $R(h^*) \le R(\hat{h})$ for the best integer $\hat{h}$. $\endgroup$ – LarrySnyder610 Sep 29 at 2:49
  • $\begingroup$ Oh, wait, maybe I see what you mean. The inequality itself isn't necessarily valid for non-integer $h$. I need to think about this more (tomorrow, when I'm more awake...) $\endgroup$ – LarrySnyder610 Sep 29 at 2:54
  • $\begingroup$ (Comment started to be written before OP's second comment)Take the simple function $f(x)=x^2-x$. If you have proven that some real value $L$ is at most as large as $f(x)$ for each integer $x$, you have proven only $L \le 0$, while your argument claims that $L \le -\frac14$. In your problem the book has proven only $T^*(X) \le R(\hat{h})$. It is also true that $R(h^*) \le R(\hat{h})$. From that does not at all follow that $T^*(X) \le R(h^*)$. $\endgroup$ – Ingix Sep 29 at 3:00
  • $\begingroup$ The construction and proof idea here seems very similar to that of Theorem 1 in Few, L. (1955). The shortest path and the shortest road through n points. Mathematika, 2(2), 141-144. While Few's proof assumes a square region, it is more rigorous (in particular about $h$ needing to be integral) and clear. I think Few's proof can easily be extended to the rectangular case, and so the analysis there can be useful here. (note that Few looks for a path through all points, but that path is easily completed to a tour) $\endgroup$ – Discrete lizard Oct 5 at 11:04
6
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Yeah, I guess the Theorem 2 argument makes sense. They do also say that Lemma 3 is a "slightly sharper result" than Theorem 2. I give this answer the slight edge over @Oguz's because of that, but they're both good answers. ;) $\endgroup$ – LarrySnyder610 Sep 29 at 1:00
7
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is an extremely good point. I have been trying to salvage their proof, but no success yet. Maybe I'll write a new question to see if anyone else can salvage it (or disprove it). $\endgroup$ – LarrySnyder610 Sep 29 at 21:30
4
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Where does the inequality $f(h) \le f\left(\sqrt{2(n-2)b/a}\right) + \frac{a}{2}$ come from? $\endgroup$ – LarrySnyder610 Oct 4 at 0:31
  • $\begingroup$ I've added some intermediate steps. $\endgroup$ – Thomas Kalinowski Oct 4 at 0:43
  • $\begingroup$ Thanks. I think this salvages the proof and is elegant. I guess I won't give the checkmark because this doesn't actually answer the original question I posed, but rather answers a question that arose in the subsequent discussion (a question that is actually far more interesting/important than my original question). $\endgroup$ – LarrySnyder610 Oct 4 at 0:59
  • $\begingroup$ Doesn't it seem weird to weaken the bound for all $n \ge 2$ just to cover the trivial case of $n=1$? I still keep wondering about that. $\endgroup$ – LarrySnyder610 Oct 4 at 1:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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