Linear interval equations: Computing enclosures with bounded relative or absolute overestimation is NP-hard.
Vladik KreinovichAnatoly V. LakeyevPublished in: Reliab. Comput. (1996)
Keyphrases
- np hard
- linear systems
- special case
- lower bound
- integer programming
- approximation algorithms
- optimal solution
- angular velocity
- square root
- linear programming
- np complete
- scheduling problem
- mathematical model
- neural network
- algebraic equations
- upper bound
- numerical solution
- finite difference
- linear equations
- constant factor approximation
- loss bounds
- set cover
- greedy heuristic
- piecewise linear
- worst case
- knapsack problem
- constraint satisfaction problems