Timeline for Traveling Salesman Problem on finite group
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 27, 2019 at 17:58 | vote | accept | Adam P. Goucher | ||
| Apr 23, 2019 at 8:48 | comment | added | Adam P. Goucher | @GerryMyerson Does there exist a polynomial $p$, such that for all groups $H$, there exists an algorithm $A_H$, such that for all norms $N_H$ on that group (with integer weights, say), $A_H$ computes an optimal tour in time bounded above by $p(n)$, where $n$ is the sum of the number of digits in all of the weights. | |
| Apr 23, 2019 at 8:27 | history | edited | Martin Sleziak |
added the (traveling-salesman-problem) tag
|
|
| Apr 23, 2019 at 8:26 | answer | added | Aaron Meyerowitz | timeline score: 3 | |
| Apr 23, 2019 at 0:56 | comment | added | Gerry Myerson | I'm not sure where the quantifiers go. Certainly if $f(x)=1$ for all $x\ne e$ there's an efficient algorithm. | |
| Apr 21, 2019 at 17:21 | comment | added | Anthony Quas | This reminds me of bell-ringing... | |
| Apr 21, 2019 at 12:21 | history | edited | Adam P. Goucher | CC BY-SA 4.0 |
Retracted the statement about Held-Karp
|
| Apr 21, 2019 at 11:02 | history | asked | Adam P. Goucher | CC BY-SA 4.0 |