Computing Exact Componentwise Bounds on Solutions of Lineary Systems with Interval Data is NP-Hard
DOI10.1137/S0895479893251198zbMATH Open0824.65011OpenAlexW2019302423MaRDI QIDQ4835403FDOQ4835403
Authors: Jiří Rohn, Vladik 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
Recommendations
- Calculation of exact bounds for the solution set of linear interval systems
- Checking bounds on solutions of linear interval equations is NP-hard
- Enclosing solutions of linear interval equations is NP-hard
- Complexity of some linear problems with interval data
- scientific article; zbMATH DE number 804135
Direct numerical methods for linear systems and matrix inversion (65F05) Analysis of algorithms and problem complexity (68Q25) Linear equations (linear algebraic aspects) (15A06) Interval and finite arithmetic (65G30)
Cited In (32)
- Solving interval linear systems with linear programming techniques
- Direct methods for linear systems with inexact input data
- Title not available (Why is that?)
- Approximate linear algebra is intractable
- Reliable modeling and optimization for chemical engineering applications: Interval analysis approach
- Solving linear interval systems is NP-hard even if we exclude overflow and underflow
- An algorithm for computing the hull of the solution set of interval linear equations
- Efficient approaches for enclosing the united solution set of the interval generalized Sylvester matrix equations
- Title not available (Why is that?)
- A bright side of NP-hardness of interval computations: Interval heuristics applied to NP-problems
- Static response analysis of structures with interval parameters using the second-order Taylor series expansion and the DCA for QB
- Checking robust nonsingularity of tridiagonal matrices in linear time
- Enclosing the solution set of parametric interval matrix equation \(A(p)X = B(p)\)
- Linear interval equations: Midpoint preconditioning may produce a 100\% overestimation for arbitrarily narrow data even in case \(n = 4\)
- Complexity issues in interval linear programming
- Centered solutions for uncertain linear equations
- How to determine basis stability in interval linear programming
- Checking bounds on solutions of linear interval equations is NP-hard
- An efficient framework for barrier certificate generation of uncertain nonlinear hybrid systems
- Vertex solution theorem for the upper and lower bounds on the dynamic response of structures with uncertain-but-bounded parameters
- Enclosing solutions of linear interval equations is NP-hard
- A comparison of metaheurisitics for the problem of solving parametric interval linear systems
- The interval Lyapunov matrix equation: analytical results and an efficient numerical technique for outer estimation of the united solution set
- Calculation of exact bounds for the solution set of linear interval systems
- Title not available (Why is that?)
- Proving endpoint dependence in solving interval parametric linear systems
- Positively regular vague matrices
- Inaccurate linear equation system with a restricted-rank error matrix
- Strong NP-completeness of a matrix similarity problem
- Why it is computationally harder to reconstruct the past than to predict the future
- On the complexity of solving feasible systems of linear inequalities specified with approximate data
- Linear interval equations: Computing enclosures with bounded relative or absolute overestimation is NP-hard
This page was built for publication: Computing Exact Componentwise Bounds on Solutions of Lineary Systems with Interval Data is NP-Hard
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4835403)
