Timeline for Finding a short path using $(0.99n)!$ permutations
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 2, 2016 at 5:36 | vote | accept | Tom Solberg | ||
| Sep 1, 2016 at 15:14 | answer | added | fedja | timeline score: 9 | |
| Sep 1, 2016 at 11:57 | comment | added | usul | Did you check, or is there an obstruction to checking, that picking your subset at random usually works? | |
| Sep 1, 2016 at 8:13 | comment | added | Tom Solberg | @DouglasZare oh, I see -- well, given that the length of the shortest path scales proportionally to $\sqrt{n}$, I'd like a path whose length is less than $c\sqrt{n}$, for some value of $c$. Does that make sense? | |
| Sep 1, 2016 at 8:00 | comment | added | Douglas Zare | Yes, it was clear that you wanted it to be short. How are you measuring whether a path of a given shortness is good? | |
| Sep 1, 2016 at 7:55 | comment | added | Tom Solberg | I want the path to have a short Euclidean length. Presumably I'd need to search all $n!$ permutations to get the shortest path, so I'd just like the Euclidean length to be "not too much longer" in some probabilistic sense. (made some minor edits to the original question to try to clarify this) | |
| Sep 1, 2016 at 7:48 | history | edited | Tom Solberg | CC BY-SA 3.0 |
added 66 characters in body
|
| Sep 1, 2016 at 7:47 | comment | added | Douglas Zare | What is your measure of how good a path is? | |
| Sep 1, 2016 at 7:38 | history | asked | Tom Solberg | CC BY-SA 3.0 |