On the hardest problem formulations for the 0/1 Lasserre hierarchy
From MaRDI portal
Publication:2976145
DOI10.1287/MOOR.2016.0797zbMATH Open1359.90088arXiv1510.01891OpenAlexW3176083298MaRDI QIDQ2976145FDOQ2976145
Authors: Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli 
Publication date: 13 April 2017
Published in: Mathematics of Operations Research (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1510.01891
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
- Sum-of-squares hierarchy lower bounds for symmetric formulations
Cites Work
- Global optimization with polynomials and the problem of moments
- On the Shannon capacity of a graph
- Sums of squares, moment matrices and optimization over polynomials
- Class of global minimum bounds of polynomial functions
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- Expander flows, geometric embeddings and graph partitioning
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Linear programming relaxations of \textsc{maxcut}
- Convex relaxations and integrality gaps
- Sum of squares lower bounds from pairwise independence (extended abstract)
- Theta bodies for polynomial ideals
- Sparse sums of squares on finite abelian groups and improved semidefinite lifts
- Lower bounds on the size of semidefinite programming relaxations
- MaxMin allocation via degree lower-bounded arborescences
- Computation of the Lasserre Ranks of Some Polytopes
- Title not available (Why is that?)
- Subexponential algorithms for unique games and related problems
- Hypercontractivity, sum-of-squares proofs, and their applications
- Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy
- CSP gaps and reductions in the lasserre hierarchy
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- Complexity of Null- and Positivstellensatz proofs
- Complexity of Positivstellensatz proofs for the knapsack
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Integrality gaps of linear and semi-definite programming relaxations for knapsack
- Rounding Semidefinite Programming Hierarchies via Global Correlation
- Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
Cited In (17)
- On inequalities with bounded coefficients and pitch for the min knapsack polytope
- Title not available (Why is that?)
- Lift \& project systems performing on the partial-vertex-cover polytope
- Computation of the Lasserre Ranks of Some Polytopes
- A multilevel analysis of the Lasserre hierarchy
- Theoretical challenges towards cutting-plane selection
- On the hardest problem formulations for the \(0/1\) Lasserre hierarchy
- High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts
- The Spectrum of the Grigoriev–Laurent Pseudomoments
- Title not available (Why is that?)
- Sum of Squares Bounds for the Empty Integral Hull Problem
- Tight sum-of-squares lower bounds for binary polynomial optimization problems
- Title not available (Why is that?)
- Breaking symmetries to rescue sum of squares: the case of makespan scheduling
- Degree Bounds for Putinar’s Positivstellensatz on the Hypercube
- Sum-of-squares hierarchy lower bounds for symmetric formulations
- Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
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)
