An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem
From MaRDI portal
Publication:1683679
DOI10.1007/s10107-016-1102-7zbMath1386.90077OpenAlexW2570315187MaRDI QIDQ1683679
Monaldo Mastrolilli, Adam Kurpisz, Samuli Leppänen
Publication date: 1 December 2017
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-016-1102-7
Related Items (7)
Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials ⋮ Sum of Squares Bounds for the Empty Integral Hull Problem ⋮ Breaking symmetries to rescue sum of squares in the case of makespan scheduling ⋮ Unnamed Item ⋮ Lift \& project systems performing on the partial-vertex-cover polytope ⋮ Unnamed Item ⋮ High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts
Cites Work
- Unnamed Item
- Unnamed Item
- Sum-of-squares hierarchy lower bounds for symmetric formulations
- Global Optimization with Polynomials and the Problem of Moments
- Convex Relaxations and Integrality Gaps
- Sum-of-squares Lower Bounds for Planted Clique
- Sum of Squares Lower Bounds from Pairwise Independence
- Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
- A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
- On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy
- Class of global minimum bounds of polynomial functions
- Faces for a linear inequality in 0–1 variables
- Tight Sum-Of-Squares Lower Bounds for Binary Polynomial Optimization Problems.
- Reducibility among Combinatorial Problems
- CSP gaps and reductions in the lasserre hierarchy
- The Geometry of Scheduling
- A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
- Computation of the Lasserre Ranks of Some Polytopes
- An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
- 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
- Approximability and proof complexity
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Complexity of Positivstellensatz proofs for the knapsack
This page was built for publication: An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem
