Tropical geometry in optimization

From CRCG-Wiki

Tropical geometry in optimization

The tropical semiring is the set of real numbers including infinity with two new operations. The tropical product of two numbers is their usual sum while their tropical sum is their maximum. For example, 3 plus 5 is 5 tropically, and 3 times five is 8. The tropical semiring can be viewed as the image of the Puiseux series field under the valuation map.

Combinatorial optimization is an immediate example of an application of the tropical semiring. Indeed computing the shortest path length between any two vertices in a metric graph amounts to computing the tropical power of a negative edge length matrix. While this is well-known as the Floyd-Warshall algorithm, it allows a generalization from the tropical perspective. Namely, the collection of polytopes in n-dimensional space form a semiring where the product of two polytopes is their Minkowski sum and their sum is the convex hull of their union. The analogue of the shortest path computation is now known as polytope propagation. Applications can be found in algebraic statistics, one being parametric alignment of DNA sequences (see here).