3 ms·

Is a superpermuation just a more efficient annotation or is it more helpful in solving an optimization problem? They talk about the travelling salesman problem

by bumby 3y ago

Is a superpermuation just a more efficient annotation or is it more helpful in solving an optimization problem? They talk about the travelling salesman problem in the article but they don't exactly explain if knowing the superpermutation helps solve it faster.

abetusk 3y ago
I'm no expert but here are my opinions: One goal is to find an 'efficient' annotation of a superposition. That is, "what is the minimum superpermutation string length of of N symbols", which itself is a sort of optimization problem. We can presumably get bounds on the minimum and maximum it can be and maybe the 'optimal' shortest superpermutation has enough variation that the bounds aren't/can't be exact. As to what "practical" applications superpermutations have, nothing comes to mind but considering how many applications de Bruijn sequences show up, I'd be surprised if they didn't start cropping up from time to time in the future. As to the travelling salesman/Hamiltonian path/cycle problem, my impression is that they used a clever construction of a Hamiltonian cycle on a hyper-cube/Cayley graph/high-dimensional-high-degree graph to show lower/upper bounds on the number of superpermutations. In other words, the implication is the other way. They construct a Hamiltonian cycle on a specially crafted graph to show lower/upper bounds rather than use superpermutations to say anything about Hamiltonian cycles. To get a flavor for how this works, I'll copy pasta the de Bruijn "construction" section of Wikipedia [0]: """ The de Bruijn sequences can be constructed by taking a Hamiltonian path of an n-dimensional de Bruijn graph over k symbols (or equivalently, an Eulerian cycle of an (n − 1)-dimensional de Bruijn graph). """ With a de Bruijn graph [1] being a specialized graph construction. [0] https://en.wikipedia.org/wiki/De_Bruijn_sequence#Construction https://en.wikipedia.org/wiki/De_Bruijn_sequence#Constructio... [1] https://en.wikipedia.org/wiki/De_Bruijn_graph https://en.wikipedia.org/wiki/De_Bruijn_graph

by bumby 3y ago

abetusk 3y ago

I'm no expert but here are my opinions: One goal is to find an 'efficient' annotation of a superposition. That is, "what is the minimum superpermutation string length of of N symbols", which itself is a sort of optimization problem. We can presumably get bounds on the minimum and maximum it can be and maybe the 'optimal' shortest superpermutation has enough variation that the bounds aren't/can't be exact. As to what "practical" applications superpermutations have, nothing comes to mind but considering how many applications de Bruijn sequences show up, I'd be surprised if they didn't start cropping up from time to time in the future. As to the travelling salesman/Hamiltonian path/cycle problem, my impression is that they used a clever construction of a Hamiltonian cycle on a hyper-cube/Cayley graph/high-dimensional-high-degree graph to show lower/upper bounds on the number of superpermutations. In other words, the implication is the other way. They construct a Hamiltonian cycle on a specially crafted graph to show lower/upper bounds rather than use superpermutations to say anything about Hamiltonian cycles. To get a flavor for how this works, I'll copy pasta the de Bruijn "construction" section of Wikipedia [0]: """ The de Bruijn sequences can be constructed by taking a Hamiltonian path of an n-dimensional de Bruijn graph over k symbols (or equivalently, an Eulerian cycle of an (n − 1)-dimensional de Bruijn graph). """ With a de Bruijn graph [1] being a specialized graph construction. [0] https://en.wikipedia.org/wiki/De_Bruijn_sequence#Construction https://en.wikipedia.org/wiki/De_Bruijn_sequence#Constructio... [1] https://en.wikipedia.org/wiki/De_Bruijn_graph https://en.wikipedia.org/wiki/De_Bruijn_graph