Application of tropical geometry to scheduling problem

Masanori Kobayashi (Tokyo Metropolitan)

Abstract

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: http://j-mi.org/contents_file/contents_files/loader/0/Article/296/file/default/JMI2013B-8.pdf