Simulating the scaling exponent in Euclidean random TSP
Take N random points in the square of area N.
Fix 0 < p < 1.
Consider the minimum-length cycle though some pN of
the points (minimized over all choices of pN points out of N).
Let
f(p,N) = (length of minimum cycle)/(pN)
be the average edge-length in the optimal cycle.
This f(p,N) is random and
depends on N, but
by easy theory
as N \to infinity with fixed p
there is a limit non-random
function f(p).
Now f(1) = approx 0.72 is an already-studied constant for the random Euclidean
traveling salesman problem. But I would like somebody to try to obtain the whole
function f(p) via simulation.
In particular,
(a) theory says the limit f(0+) is strictly > 0; estimate it numerically.
(b) statistical physics suggests a scaling exponent \alpha:
f(p) - f(0+) scales as p^\alpha for small p
estimate \alpha.
(November 2006) I have done
some crude simulations myself, but these are far too crude to help with the scaling exponent question.