10
$\begingroup$

This is inspired by a recent question.

Given a positive integer $n\in\mathbb{N}$, is there a setting of finitely many points and a designated "starting point" $s$ in $\mathbb{R}^2$ such that the nearest-neighbor algorithm (described below) gives a tour that is $n$ times longer than the optimal solution starting at $s$?

Starting at $s$, pick the nearest neighbor not visited so far as the next node to visit.

EDIT: If the answer is no, what is the maximum value that the ratio $r$ of "nearest neighbor trip" vs "best trip" can take?

Improve this question
$\endgroup$
7
  • $\begingroup$ Does not exist. It all depends on the position of the points. You can even choose the location that this algorithm is optimal. $\endgroup$
    – individ
    Commented Jun 26, 2015 at 6:46
  • $\begingroup$ So what is the biggest factor nearest neighbor trip vs best trip can take? $\endgroup$
    – Dominic van der Zypen
    Commented Jun 26, 2015 at 6:48
  • $\begingroup$ Should the task of paraphrase. Takes a random number of points $n$ they randomly have on the plane. And with some random points start to crawl by this algorithm outperforming all points. And need to know the mathematical expectation of how many times it is not effective? The number of points does not play any role. $\endgroup$
    – individ
    Commented Jun 26, 2015 at 7:01
  • 1
    $\begingroup$ See the answer to this question: cstheory.stackexchange.com/questions/18307/… $\endgroup$
    – Gordon Royle
    Commented Jun 26, 2015 at 10:03
  • $\begingroup$ Thanks - can you make this into an answer, please? $\endgroup$
    – Dominic van der Zypen
    Commented Jun 26, 2015 at 11:31

1 Answer 1

Reset to default
15
$\begingroup$

The nearest-neighbor (NN) heuristic (among others) is analyzed in this paper:

Johnson, David S., and Lyle A. McGeoch. "The traveling salesman problem: A case study in local optimization." Local search in combinatorial optimization 1 (1997): 215-310. (PDF download link.)

They say:

JMcG
In the specific case of "random Euclidean instances" (in contrast to "random distance matrices"), they observe experimentally a fixed ~25% longer path length, which would exceed any fixed $n$ for large enough nodes $N$. In terms of both theory and experiments with random distance matrices, the growth rate is $\log N$. Either way, any fixed $n$ could be exceeded with sufficiently large $N$, so the answer to the OP's question is Yes.

The cited paper is: Rosenkrantz, Daniel J., Richard E. Stearns, and Philip M. Lewis, II. "An analysis of several heuristics for the traveling salesman problem." SIAM Journal on Computing 6.3 (1977): 563-581. (Journal link.)

Added (in response to question from Manfred). Here is the essence of the Rosenkrantz et al. lower bound:
         
          (Slide from David Johnson PowerPoint Lecture.)

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Doesn't that mean that the answer to the first question is Yes? Given $n$, we can always choose $N$ so that $0.5(\lceil \log_2N\rceil+1) > n$. $\endgroup$
    – TonyK
    Commented Jun 26, 2015 at 13:44
  • $\begingroup$ @TonyK: Oh, you are right, I was mixing $n$ with $N$. :-) $\endgroup$
    – Joseph O'Rourke
    Commented Jun 26, 2015 at 13:59
  • 1
    $\begingroup$ Doesn't the paper refer to the metric TSP, whereas the OP is asking about the special case of TSP in the plane? $\endgroup$
    – Bill Bradley
    Commented Jun 26, 2015 at 14:27
  • $\begingroup$ @BillBradley: Good point. In the Johnson-McGeoch experimental results (p.15), they distinguish between "random Euclidean instances" and "random distance matrices." The former approach a fixed 25% longer than the K-H lower bound. I will correct my answer. $\endgroup$
    – Joseph O'Rourke
    Commented Jun 26, 2015 at 14:36
  • $\begingroup$ You're still saying No... $\endgroup$
    – TonyK
    Commented Jun 26, 2015 at 14:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .