Minimax algebra and applications

The paper considers theories of linear and of polynomial algebra, over two scalar systems, often called max-algebra and min-algebra. Here, max-algebra is the system M=(ℝℝ{¸-•},ℝpound;,ª$) where xℝpound;y=max(x,y) and xª$y=x+y. Min-algebra is the dual system M'=(ℝℝ{¸+•},¸ℝpound;',¸ª$') with x¸ℝpound;'y=min(x,y) and x¸ª$'y=x+y. Towards the end the paper also considers minimum algebra, the system M“=(ℝℝ{¸-•,¸+•}, ¸ℝpound;,¸ª$,¸ℝpound;',¸ª$'). Application fields discussed include location problems, machine scheduling, cutting and packing problems, discrete-event systems and path-finding problems.