Idempotent mathematics and interval analysis

Idempotent mathematics, which is based on the so-called idempotent superposition principle, has achieved a significant role lately in applications to problems of optimization (optimization of graphs, discrete optimization with a large parameter, optimal organization of parallel computation, etc.). However, in practice one often deals with uncertain data so that the use of interval arithmetic (which transfers the operations with numbers to operations with sets) facilitates the work with unreliable data and the control of rounding error through the process of computation. For these reasons the authors of this extensive paper develop an analogue of interval analysis in the context of optimization theory and idempotent mathematics, that is, a generalization of idempotent mathematics for the case of operations with sets. Different kinds of interval extensions of idempotent semi-rings (the weak interval extension, interval extension with a zero element) and their properties are discussed. par It is shown that idempotent interval arithmetic has much better behavior compared to classical situation, such as the distributivity property, associativity of matrix multiplication and a polynomial number of operations in solving interval systems of linear equations. This makes this structure suitable for applications in linear algebra and even further. Namely, idempotent linear algebra lies in the essence of idempotent analysis since by the principle of superposition many nonlinear algorithms can be suitably approximated by linear algorithms. Such applications are also considered in the paper.