Exact interval solutions to the discrete Bellman equation and polynomial complexity of problems in interval idempotent linear algebra

Details Exact interval solutions to the discrete Bellman equation and polynomial complexity of problems in interval idempotent linear algebra Exact interval solutions to the discrete Bellman equation and polynomial complexity of problems in interval idempotent linear algebra

2001-01-05

arxiv.org/abs/math/0101041v3

Doklady Akademii Nauk 374:3 (2000) 304-306; Eng. transl. in Doklady Mathematics 62:2 (2000) 199-201

Mathematics

Rings and Algebras

8 pages, no figures; it's an English translation of the Russian publication indicated below, with a number of minor stylistica

Scientific paper

In this note we construct a solution of a matrix interval linear equation of the form X=AX+B (the discrete stationary Bellman equation) over partially ordered semirings, including the semiring of nonnegative real numbers and all idempotent semirings. We discuss also the computational complexity of problems in interval idempotent linear algebra. In the traditional Interval Analysis problems of this kind are generally NP-hard. In the note we consider matrix equations over positive semirings; in this case the computational complexity of the problem is polynomial. Idempotent and other positive semirings arise naturally in optimization problems. Many of these problems turn out to be linear over appropriate idempotent semirings. In this case, the system of equations X=AX+B appears to be a natural analog of a usual linear system in the traditional linear algebra over fields. B. A. Carre showed that many of the well-known algorithms of discrete optimization are analogous to standard algorithms of the traditional computational linear algebra.

Affiliated with

Also associated with

No associations

Rating

Exact interval solutions to the discrete Bellman equation and polynomial complexity of problems in interval idempotent linear algebra does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Exact interval solutions to the discrete Bellman equation and polynomial complexity of problems in interval idempotent linear algebra, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exact interval solutions to the discrete Bellman equation and polynomial complexity of problems in interval idempotent linear algebra will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-120278