Minimax Algebra

A number of different problems of interest to the operational researcher and the mathematical economist - for example, certain problems of optimization on graphs and networks, of machine-scheduling, of convex analysis and of approx- imation theory - can be formulated in a convenient way using the algebraic structure (R,$,@) where we may think of R as the (extended) real-number system with the binary combining operations x$y, x(R)y defined to be max(x,y),(x+y) respectively. The use of this algebraic structure gives these problems the character of problems of linear algebra, or linear operator theory. This fact hB.s been independently discovered by a number of people working in various fields and in different notations, and the starting-point for the present Lecture Notes was the writer's persuasion that the time had arrived to present a unified account of the algebra of linear transformations of spaces of n-tuples over (R,$,(R)),to demonstrate its relevance to operational research and to give solutions to the standard linear-algebraic problems which arise - e.g. the solution of linear equations exactly or approximately, the eigenvector- eigenvalue problem andso on.Some of this material contains results of hitherto unpublished research carried out by the writer during the years 1970-1977.