Universal algorithms for solving the matrix Bellman equations over semirings

DOI10.1007/S00500-013-1027-5zbMATH Open1327.65082arXiv1209.5011OpenAlexW2073784872MaRDI QIDQ889976FDOQ889976

Authors: A. Ya. Rodionov, S. N. Sergeev, Grigori L. Litvinov, Andrei Sobolevski 

Publication date: 9 November 2015

Published in: Soft Computing (Search for Journal in Brave)

Abstract: This paper is a survey on universal algorithms for solving the matrix Bellman equations over semirings and especially tropical and idempotent semirings. However, original algorithms are also presented. Some applications and software implementations are discussed.

Full work available at URL: https://arxiv.org/abs/1209.5011

Recommendations

• Exact interval solutions of the discrete Bellman equation, and the polynomial complexity of problems in interval idempotent linear algebra.
• Methods and applications of \((\max,+)\) linear algebra
• scientific article; zbMATH DE number 1136259
• Idempotent/tropical analysis, the Hamilton-Jacobi and Bellman equations
• Universal numerical algorithms and their software implementation

zbMATH Keywords

semiringmatrix Bellman equationtropical and idempotent semiringsuniversal algorithms

Mathematics Subject Classification ID

Max-plus and related algebras (15A80) Computational aspects of associative rings (general theory) (16Z05) Matrix equations and identities (15A24) Semirings (16Y60)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Max-linear systems. Theory and algorithms.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computational methods of linear algebra
• Minimax algebra
• Title not available (Why is that?)
• Interval Methods for Systems of Equations
• Title not available (Why is that?)
• Linear Optimization Problems with Inexact Data
• Graphs, dioids and semirings. New models and algorithms.
• On a new principle of superposition for optimization problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tropical geometry and its applications
• An Algebra for Network Routing Problems
• Idempotent functional analysis: An algebraic approach
• Computational complexity and feasibility of data processing and interval computations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Control solvability of interval systems of max-separable linear equations
• Interval systems of max-separable linear equations
• Idempotent interval analysis and optimization problems
• Interval systems of max-separable linear equations
• Regular Algebra Applied to Path-finding Problems
• From the sixteenth Hilbert problem to tropical geometry
• Interval systems over idempotent semiring
• Z-matrix equations in max-algebra, nonnegative linear algebra and other semirings
• Title not available (Why is that?)
• A systolic array algorithm for the algebraic path problem (shortest paths; matrix inversion)
• Optimale Lösung von Intervallgleichungssystemen
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algebraic structures for transitive closure
• Universal numerical algorithms and their software implementation
• Interval arithmetic and linear algebra over idempotent semirings.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Idempotent mathematics: a correspondence principle and its applications to computing

Cited In (8)

• The Markov chain tree theorem in commutative semirings and the state reduction algorithm in commutative semifields
• A velocity-combined local best particle swarm optimization algorithm for nonlinear equations
• Exact interval solutions of the discrete Bellman equation, and the polynomial complexity of problems in interval idempotent linear algebra.
• A cubic time algorithm for finding the principal solution to Sylvester matrix equations over (max, +)
• Ideal basis in constructions defined by directed graphs
• Artificial Intelligence and Symbolic Computation
• Universal numerical algorithms and their software implementation
• On pseudo-inverses of matrices and their characteristic polynomials in supertropical algebra

This page was built for publication: Universal algorithms for solving the matrix Bellman equations over semirings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q889976)