Return to Answer

A careful experimental analysis of the nearest-neighbor (NN) heuristic (among other heuristics) is described 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 find that the growth rate, in comparison to the Karp-Held lower bound, "appears to be proportional to $\log n$" for "random distance matrices." This is the theoretical growth rate w.r.t. the optimum. In contrast, for "random Euclidean instances" up to $n=10^6$, they find (Table 1, p.15) that the NN heuristic leads to paths nearly constantly about 25% longer than the Karp-Held lower bound. This is closer (but not identical) to the OP's "uniformly distributed within $[0,1]^2$." The section, "Standard Test Instances" on pp.12-14 unpacks "random Euclidean instances."

Incidentally, the observed running time grows subquadratically.

(See also the follow-up MO question, "Travelling Salesman Problem: Can the nearest neighbor algorithm be n times longer than the optimal solution?.")

A careful experimental analysis of the nearest-neighbor (NN) heuristic (among other heuristics) is described 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 find that the growth rate, in comparison to the Karp-Held lower bound, "appears to be proportional to $\log n$" for "random distance matrices." This is the theoretical growth rate w.r.t. the optimum. In contrast, for "random Euclidean instances" up to $n=10^6$, they find (Table 1, p.15) that the NN heuristic leads to paths nearly constantly about 25% longer than the Karp-Held lower bound. This is closer (but not identical) to the OP's "uniformly distributed within $[0,1]^2$." The section, "Standard Test Instances" on pp.12-14 unpacks "random Euclidean instances."

Incidentally, the observed running time grows subquadratically.

(See also the follow-up MO question, "Travelling Salesman Problem: Can the nearest neighbor algorithm be n times longer than the optimal solution?.")

A careful experimental analysis of the nearest-neighbor (NN) heuristic (among other heuristics) is described 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 find that the growth rate, in comparison to the Karp-Held lower bound, "appears to be proportional to $\log n$" for "random distance matrices." This is the theoretical growth rate w.r.t. the optimum. In contrast, for "random Euclidean instances" up to $n=10^6$, they find (Table 1) that the NN heuristic leads to paths nearly constantly about 25% longer than the Karp-Held lower bound. Incidentally, the observed running time grows subquadratically.

(See also the follow-up MO question, "Travelling Salesman Problem: Can the nearest neighbor algorithm be n times longer than the optimal solution?.")

A careful experimental analysis of the nearest-neighbor (NN) heuristic (among other heuristics) is described 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 find that the growth rate, in comparison to the Karp-Held lower bound, "appears to be proportional to $\log n$" for "random distance matrices." This is the theoretical growth rate w.r.t. the optimum. In contrast, for "random Euclidean instances" up to $n=10^6$, they find (Table 1, p.15) that the NN heuristic leads to paths nearly constantly about 25% longer than the Karp-Held lower bound. This is closer (but not identical) to the OP's "uniformly distributed within $[0,1]^2$." The section, "Standard Test Instances" on pp.12-14 unpacks "random Euclidean instances."

Incidentally, the observed running time grows subquadratically.

(See also the follow-up MO question, "Travelling Salesman Problem: Can the nearest neighbor algorithm be n times longer than the optimal solution?.")

A careful experimental analysis of the nearest-neighbor (NN) heuristic (among other heuristics) is described 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 find that the growth rate, in comparison to the Karp-Held lower bound, "appears to be proporotional to $\log n$." This is the theoretical growth rate w.r.t. the optimum. In particular, for random Euclidean instances up to $n=10^6$, they find (Table 1) that the NN heuristic leads to paths about 25% longer than the Karp-Held lower bound. Incidentally, the observed running time grows subquadratically.

(See also the follow-up MO question, "Travelling Salesman Problem: Can the nearest neighbor algorithm be n times longer than the optimal solution?.")

A careful experimental analysis of the nearest-neighbor (NN) heuristic (among other heuristics) is described 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 find that the growth rate, in comparison to the Karp-Held lower bound, "appears to be proportional to $\log n$" for "random distance matrices." This is the theoretical growth rate w.r.t. the optimum. In contrast, for "random Euclidean instances" up to $n=10^6$, they find (Table 1) that the NN heuristic leads to paths nearly constantly about 25% longer than the Karp-Held lower bound. Incidentally, the observed running time grows subquadratically.

(See also the follow-up MO question, "Travelling Salesman Problem: Can the nearest neighbor algorithm be n times longer than the optimal solution?.")