Tight Sum-Of-Squares Lower Bounds for Binary Polynomial Optimization Problems.
From MaRDI portal
Publication:4598218
DOI10.4230/LIPIcs.ICALP.2016.78zbMath1388.90094arXiv1605.03019OpenAlexW2963033151MaRDI QIDQ4598218
Monaldo Mastrolilli, Samuli Leppänen, Adam Kurpisz
Publication date: 19 December 2017
Full work available at URL: https://arxiv.org/abs/1605.03019
Semidefinite programming (90C22) Integer programming (90C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (9)
Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators ⋮ An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem ⋮ Sum of Squares Bounds for the Empty Integral Hull Problem ⋮ Sum-of-squares hierarchy lower bounds for symmetric formulations ⋮ Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems ⋮ Unnamed Item ⋮ Sum-of-squares hierarchies for binary polynomial optimization ⋮ Sum-of-squares hierarchies for binary polynomial optimization ⋮ High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts
This page was built for publication: Tight Sum-Of-Squares Lower Bounds for Binary Polynomial Optimization Problems.
