Improved Approximation Lower Bounds on Small Occurrence Optimization
Piotr BermanMarek KarpinskiPublished in: Electron. Colloquium Comput. Complex. (2003)
Keyphrases
- lower bound
- min sum
- upper bound
- objective function
- global optimization
- branch and bound
- optimization problems
- branch and bound algorithm
- worst case
- approximation algorithms
- optimization process
- optimization algorithm
- np hard
- small number
- constrained optimization
- optimization model
- improved algorithm
- learning algorithm
- efficient computation
- combinatorial optimization
- vc dimension
- approximation error
- linear programming relaxation
- approximation methods
- optimal solution
- integrality gap
- bayes error rate