On the hardest problem formulations for the 0/1 Lasserre hierarchy
From MaRDI portal
Publication:2976145
Abstract: The Lasserre/Sum-of-Squares (SoS) hierarchy is a systematic procedure for constructing a sequence of increasingly tight semidefinite relaxations. It is known that the hierarchy converges to the 0/1 polytope in n levels and captures the convex relaxations used in the best available approximation algorithms for a wide variety of optimization problems. In this paper we characterize the set of 0/1 integer linear problems and unconstrained 0/1 polynomial optimization problems that can still have an integrality gap at level n-1. These problems are the hardest for the Lasserre hierarchy in this sense.
Recommendations
- On the hardest problem formulations for the \(0/1\) Lasserre hierarchy
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems
- A multilevel analysis of the Lasserre hierarchy
Cites work
- scientific article; zbMATH DE number 2086404 (Why is no real title available?)
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- CSP gaps and reductions in the lasserre hierarchy
- Class of global minimum bounds of polynomial functions
- Complexity of Null- and Positivstellensatz proofs
- Complexity of Positivstellensatz proofs for the knapsack
- Computation of the Lasserre Ranks of Some Polytopes
- Convex relaxations and integrality gaps
- Expander flows, geometric embeddings and graph partitioning
- Global optimization with polynomials and the problem of moments
- Hypercontractivity, sum-of-squares proofs, and their applications
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Integrality gaps of linear and semi-definite programming relaxations for knapsack
- Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Linear programming relaxations of \textsc{maxcut}
- Lower bounds on the size of semidefinite programming relaxations
- MaxMin allocation via degree lower-bounded arborescences
- On the Shannon capacity of a graph
- Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy
- Rounding Semidefinite Programming Hierarchies via Global Correlation
- Sparse sums of squares on finite abelian groups and improved semidefinite lifts
- Subexponential algorithms for unique games and related problems
- Sum of squares lower bounds from pairwise independence (extended abstract)
- Sums of squares, moment matrices and optimization over polynomials
- Theta bodies for polynomial ideals
Cited in
(15)- Sum-of-squares bounds via Boolean function analysis
- scientific article; zbMATH DE number 2102750 (Why is no real title available?)
- Lift \& project systems performing on the partial-vertex-cover polytope
- Degree Bounds for Putinar’s Positivstellensatz on the Hypercube
- Computation of the Lasserre Ranks of Some Polytopes
- scientific article; zbMATH DE number 7378399 (Why is no real title available?)
- On inequalities with bounded coefficients and pitch for the min knapsack polytope
- Theoretical challenges towards cutting-plane selection
- Sum of Squares Bounds for the Empty Integral Hull Problem
- A multilevel analysis of the Lasserre hierarchy
- Tight sum-of-squares lower bounds for binary polynomial optimization problems
- High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts
- On the hardest problem formulations for the \(0/1\) Lasserre hierarchy
- Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
- The Spectrum of the Grigoriev–Laurent Pseudomoments
This page was built for publication: On the hardest problem formulations for the 0/1 Lasserre hierarchy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976145)
