Computing Exact Componentwise Bounds on Solutions of Lineary Systems with Interval Data is NP-Hard
From MaRDI portal
Publication:4835403
DOI10.1137/S0895479893251198zbMath0824.65011OpenAlexW2019302423MaRDI QIDQ4835403
Jiří Rohn, Vladik Ya. Kreinovich
Publication date: 14 June 1995
Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0895479893251198
Analysis of algorithms and problem complexity (68Q25) Interval and finite arithmetic (65G30) Direct numerical methods for linear systems and matrix inversion (65F05) Linear equations (linear algebraic aspects) (15A06)
Related Items (27)
Enclosing solutions of linear interval equations is NP-hard ⋮ Checking bounds on solutions of linear interval equations is NP-hard ⋮ Direct methods for linear systems with inexact input data ⋮ Enclosing the solution set of parametric interval matrix equation \(A(p)X = B(p)\) ⋮ Reliable modeling and optimization for chemical engineering applications: Interval analysis approach ⋮ A bright side of NP-hardness of interval computations: Interval heuristics applied to NP-problems ⋮ Vertex solution theorem for the upper and lower bounds on the dynamic response of structures with uncertain-but-bounded parameters ⋮ Checking robust nonsingularity of tridiagonal matrices in linear time ⋮ Why it is computationally harder to reconstruct the past than to predict the future ⋮ An efficient framework for barrier certificate generation of uncertain nonlinear hybrid systems ⋮ The interval Lyapunov matrix equation: analytical results and an efficient numerical technique for outer estimation of the united solution set ⋮ Efficient approaches for enclosing the united solution set of the interval generalized Sylvester matrix equations ⋮ An algorithm for computing the hull of the solution set of interval linear equations ⋮ How to determine basis stability in interval linear programming ⋮ Unnamed Item ⋮ Proving endpoint dependence in solving interval parametric linear systems ⋮ Strong NP-completeness of a matrix similarity problem ⋮ Linear interval equations: Computing enclosures with bounded relative or absolute overestimation is NP-hard ⋮ Positively regular vague matrices ⋮ Linear interval equations: Midpoint preconditioning may produce a 100\% overestimation for arbitrarily narrow data even in case \(n = 4\) ⋮ Centered solutions for uncertain linear equations ⋮ Calculation of exact bounds for the solution set of linear interval systems ⋮ A Comparison of Metaheurisitics for the Problem of Solving Parametric Interval Linear Systems ⋮ Static response analysis of structures with interval parameters using the second-order Taylor series expansion and the DCA for QB ⋮ Solving interval linear systems with linear programming techniques ⋮ Inaccurate linear equation system with a restricted-rank error matrix ⋮ Unnamed Item
This page was built for publication: Computing Exact Componentwise Bounds on Solutions of Lineary Systems with Interval Data is NP-Hard
