Application of tropical geometry to scheduling problem

Masanori Kobayashi (Tokyo Metropolitan)


Max-Plus (tropical) algebra has long been used in many areas such as computer science and modern control theory, which includes scheduling problems. Tropical geometry emerged as a polyhedral geometry with Max-Plus algebra, where a tropical polynomial determines a PL set, a tropical hypersurface, which is topologically a dual complex of a regular subdivision of its Newton polytope. I will talk how this geometric perspective is useful in the context of a scheduling problem, starting from the basics. This is a joint work with S. Odagiri. The basic part can be seen in: