Integrality Gaps of Linear and Semi-definite Programming Relaxations for Knapsack

Anna R. Karlin Claire Mathieu C. Thach Nguyen

Published in: CoRR (2010)

Keyphrases

semidefinite
semi definite programming
lp relaxation
semidefinite programming
linear systems
linear programming
knapsack problem

convex relaxation
feasible solution
optimal solution
sufficient conditions
linear programming relaxation
dynamic programming
interior point methods

upper bound
integer programming
convex sets
higher dimensional
lower bound
convex optimization
np hard

mixed integer
quadratic programming
column generation
feature selection
multistage
training data