Skip to main content
added 35 characters in body
Source Link

In the big picture, I'd like to know: if I sample $n$ points uniformly at random in the unit square, what is the probability that the shortest path throughthat visits each one of them is very small?

More precisely: if I sample $n$ points uniformly at random in the unit square, then it is known that as $n$ becomes large, the shortest path $L_n$ through these points satisfies

$$L_n/\sqrt{n} \to \beta \approx 0.71~,$$

with probability one, where $\beta$ is the "Euclidean TSP constant". My question is: for a given (small) length $\ell$, say $\ell = c\sqrt{n}$ for small $c<\beta$ , does a non-trivial lower bound for $\Pr(L_n \leq \ell)$ exist?

In the big picture, I'd like to know: if I sample $n$ points uniformly at random, what is the probability that the shortest path through them is very small?

More precisely: if I sample $n$ points uniformly at random in the unit square, then it is known that as $n$ becomes large, the shortest path $L_n$ through these points satisfies

$$L_n/\sqrt{n} \to \beta \approx 0.71~,$$

with probability one, where $\beta$ is the "Euclidean TSP constant". My question is: for a given (small) length $\ell$, say $\ell = c\sqrt{n}$ for small $c<\beta$ , does a non-trivial lower bound for $\Pr(L_n \leq \ell)$ exist?

In the big picture, I'd like to know: if I sample $n$ points uniformly at random in the unit square, what is the probability that the shortest path that visits each one of them is very small?

More precisely: if I sample $n$ points uniformly at random in the unit square, then it is known that as $n$ becomes large, the shortest path $L_n$ through these points satisfies

$$L_n/\sqrt{n} \to \beta \approx 0.71~,$$

with probability one, where $\beta$ is the "Euclidean TSP constant". My question is: for a given (small) length $\ell$, say $\ell = c\sqrt{n}$ for small $c<\beta$ , does a non-trivial lower bound for $\Pr(L_n \leq \ell)$ exist?

Source Link

The distribution of the shortest path through $n$ points

In the big picture, I'd like to know: if I sample $n$ points uniformly at random, what is the probability that the shortest path through them is very small?

More precisely: if I sample $n$ points uniformly at random in the unit square, then it is known that as $n$ becomes large, the shortest path $L_n$ through these points satisfies

$$L_n/\sqrt{n} \to \beta \approx 0.71~,$$

with probability one, where $\beta$ is the "Euclidean TSP constant". My question is: for a given (small) length $\ell$, say $\ell = c\sqrt{n}$ for small $c<\beta$ , does a non-trivial lower bound for $\Pr(L_n \leq \ell)$ exist?