Complexity Lower Bounds for Approximation Algebraic Computation Trees.
Felipe CuckerDima GrigorievPublished in: J. Complex. (1999)
Keyphrases
- lower bound
- approximation error
- worst case
- upper bound
- efficient computation
- decision trees
- increase in computational complexity
- np hard
- branch and bound
- approximation algorithms
- computational complexity
- objective function
- error bounds
- branch and bound algorithm
- linear algebra
- quadratic assignment problem
- exact computation
- average case complexity
- np complete
- space complexity
- model selection
- lower and upper bounds
- linear programming relaxation
- constant factor