Timeline for Shortest path through $n^{1/3}$ points out of $n$
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 2, 2016 at 3:27 | answer | added | Douglas Zare | timeline score: 3 | |
| Mar 31, 2016 at 17:21 | comment | added | Kellar | Good point; you're right, the upper bounding arguments do not present a problem. I guess it's the lower bound that's giving me trouble. | |
| Mar 31, 2016 at 12:54 | answer | added | user44143 | timeline score: 6 | |
| Mar 31, 2016 at 9:34 | comment | added | Fedor Petrov | I think, they should scale pretty well. Maximal path with all coordinates increasing is about $c n^{1/3}$ for some $c>1$. It is concentrated near diagonal. This gives $\sqrt{3}$ for modified problem, as in Ofer's comment. | |
| Mar 31, 2016 at 8:50 | review | First posts | |||
| Mar 31, 2016 at 8:51 | |||||
| Mar 31, 2016 at 8:49 | history | asked | Kellar | CC BY-SA 3.0 |