Sum-of-squares hierarchies for binary polynomial optimization
From MaRDI portal
Publication:5918420
DOI10.1007/978-3-030-73879-2_4zbMath1482.90142arXiv2011.04027OpenAlexW3162261347MaRDI QIDQ5918420
Publication date: 21 December 2021
Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2011.04027
semidefinite programmingFourier analysisKrawtchouk polynomialsLasserre hierarchysum-of-squares polynomialspolynomial kernelsbinary polynomial optimization
Related Items
Sum-of-Squares Hierarchies for Polynomial Optimization and the Christoffel--Darboux Kernel, Harmonic Hierarchies for Polynomial Optimization, Sum-of-squares hierarchies for binary polynomial optimization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sparse sums of squares on finite abelian groups and improved semidefinite lifts
- Polyhedral and semidefinite programming methods in combinatorial optimization
- Correlation clustering
- On the complexity of Putinar's Positivstellensatz
- On the complexity of Schmüdgen's Positivstellensatz
- A MAX-CUT formulation of 0/1 programs
- Uniform denominators in Hilbert's seventeenth problem
- Near-optimal analysis of Lasserre's univariate measure-based bounds for multivariate polynomial optimization
- Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere
- Improved convergence analysis of Lasserre's measure-based upper bounds for polynomial minimization on compact sets
- The sum-of-squares hierarchy on the sphere and applications in quantum information theory
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- Global Optimization with Polynomials and the Problem of Moments
- Lower Bounds on the Size of Semidefinite Programming Relaxations
- Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
- A New Look at Nonnegativity on Closed Sets and Polynomial Optimization
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A Survey of Semidefinite Programming Approaches to the Generalized Problem of Moments and Their Error Analysis
- Approximating the cut-norm via Grothendieck's inequality
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Sum-of-squares proofs and the quest toward optimal algorithms
- Tight Sum-Of-Squares Lower Bounds for Binary Polynomial Optimization Problems.
- SOS Is Not Obviously Automatizable, Even Approximately
- Worst-Case Examples for Lasserre’s Measure–Based Hierarchy for Polynomial Optimization on the Hypercube
- On the Bit Complexity of Sum-of-Squares Proofs
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
- Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems
- Sum-of-squares hierarchies for binary polynomial optimization
