Complexity of some linear problems with interval data

DOI10.1023/A:1009987227018zbMath0888.65052OpenAlexW138170242MaRDI QIDQ1371175

Jiří Rohn

Publication date: 4 June 1998

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

Full work available at URL: https://doi.org/10.1023/a:1009987227018

zbMATH Keywords

complexityinterval arithmeticNP-hardpolynomial timelinear or quadratic optimizationsystems of linear equations or inequalities

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Quadratic programming (90C20) Linear programming (90C05) Interval and finite arithmetic (65G30) Complexity and performance of numerical algorithms (65Y20) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items

The Worst Case Finite Optimal Value in Interval Linear Programming, On the optimal solution set in interval linear programming, A survey of computational complexity results in systems and control, Control solvability of interval systems of max-separable linear equations, Interval max-plus matrix equations, Duality gap in interval linear programming, Testing weak optimality of a given solution in interval linear programming revisited: NP-hardness proof, algorithm and some polynomially-solvable cases, Checking weak optimality and strong boundedness in interval linear programming, Computing the norm ∥A∥∞,1 is NP-hard^∗, Unnamed Item, Unnamed Item

Uses Software

• mctoolbox