From Algebra to Algorithms

Continuous generalization of the traveling salesman problem (TSP).

Tour starts and ends at the same point, covers every point.

- Galois groups
- Abelian property
- Polyminoes
- Minkowski sums

**Polynomials are solvable by radicals iff they have enough symmetry.**

**i.e. iff their Galois group is abelian (commutative)**

Polynomials of order < 5 are algebraically **easy**

- Can be solved by radicals

\( \frac{-b \pm \sqrt{b^2-4ac}}{2a} \)

Most polynomials of order ≥ 5 are algebraically **hard**

- Cannot be solved by radicals

Generalized dominoes.

Shapes made up of pixels.

\( {\color{red} R} = {\color{green} G} \bigoplus {\color{blue} B} = \{ \mathbf g + \mathbf b\ |\ \mathbf g \in {\color{green} G},\ \mathbf b \in {\color{blue} B} \} \)

Problem is now reduced to the traveling salesperson problem. **Solution:**

- Integer Programming (IP)
- Large Neighborhood Search (LNS)

**Already proven:**

- the optimal tour of a polygon is polygonal itself

**Proven in this paper**

- the coordinates are algebraically hard

**Future research:**

- Better lower bounds