Sum-of-squares hierarchy lower bounds for symmetric formulations.
Adam KurpiszSamuli LeppänenMonaldo MastrolilliPublished in: Electron. Colloquium Comput. Complex. (2016)
Keyphrases
- lower bound
- integer programming formulations
- upper bound
- branch and bound algorithm
- np hard
- branch and bound
- objective function
- upper and lower bounds
- cutting plane
- optimal solution
- lower bounding
- mixed integer linear programming
- optimal cost
- lower and upper bounds
- valid inequalities
- hierarchical structure
- higher level
- vc dimension
- quadratic assignment problem
- integer programming
- lower level
- randomly generated problems
- similarity measure