Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures.
Toniann PitassiNathan SegerlindPublished in: SODA (2009)
Keyphrases
- lower bound
- upper bound
- linear programming relaxation
- average case complexity
- tree structure
- branch and bound algorithm
- objective function
- branch and bound
- tree structures
- worst case
- np hard
- binary tree
- lower and upper bounds
- upper and lower bounds
- cutting plane
- mixed integer
- vc dimension
- integer programming
- index structure
- linear systems
- special case
- optimal cost
- stable set