Timeline for Shortest path through $\sqrt{n}$ points out of $n$
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 17, 2014 at 2:46 | comment | added | ofer zeitouni | In fact, for the modified problem I defined (path starting at (0,0) and ending at (1,1), $\sqrt{2}$ is a trivial lower bound and also an upper bound from the LIS analysis. So for that modified problem, $\sqrt{2}$ is the correct answer. | |
| Jul 16, 2014 at 23:05 | vote | accept | Kellar | ||
| Jul 16, 2014 at 18:28 | comment | added | Christian Remling | John's argument applies to a worst case scenario. For what it's worth, I'd be quite surprised if with the additional randomness from the OP, the quantity in question didn't go to zero. (For example, this would follow if it could be shown that suitably selected $n/4$ points cluster in a square of sidelength $q$, for a fixed $q<1/2$.) | |
| Jul 16, 2014 at 16:53 | comment | added | John Gunnar Carlsson | (continued) This tells us that $\kappa$ (whatever its value is) is also a valid bound for the quantity of interest, which is less than $\sqrt{2}$. | |
| Jul 16, 2014 at 16:53 | comment | added | John Gunnar Carlsson | Actually, the $\sqrt{2}$ is a fairly weak upper bound and can be improved by using the Beardwood-Halton-Hammersley theorem, which says that for a sufficiently large set of uniform samples in the unit square, we have $L_n/\sqrt{n} \rightarrow \kappa$ (almost surely), where $L_n$ represents the TSP tour of $n$ points, and $\kappa$ is the "TSP constant" which is known to satisfy $0.6250\leq\kappa\leq0.9204$, and it is conjectured that $\kappa \approx 0.7124$. This is described in formulas (18) and (19) of mathworld.wolfram.com/TravelingSalesmanConstants.html. | |
| Jul 16, 2014 at 4:17 | vote | accept | Kellar | ||
| Jul 16, 2014 at 4:17 | |||||
| Jul 16, 2014 at 3:08 | history | edited | ofer zeitouni | CC BY-SA 3.0 |
added 26 characters in body
|
| Jul 16, 2014 at 0:23 | history | answered | ofer zeitouni | CC BY-SA 3.0 |