On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy
From MaRDI portal
Publication:2976145
DOI10.1287/moor.2016.0797zbMath1359.90088arXiv1510.01891MaRDI QIDQ2976145
Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli
Publication date: 13 April 2017
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1510.01891
Related Items
Unnamed Item, Unnamed Item, High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts, Sum of Squares Bounds for the Empty Integral Hull Problem, The Spectrum of the Grigoriev–Laurent Pseudomoments, Degree Bounds for Putinar’s Positivstellensatz on the Hypercube, Theoretical challenges towards cutting-plane selection, Lift \& project systems performing on the partial-vertex-cover polytope, Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials, Breaking symmetries to rescue sum of squares in the case of makespan scheduling, On inequalities with bounded coefficients and pitch for the min knapsack polytope
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sparse sums of squares on finite abelian groups and improved semidefinite lifts
- Global Optimization with Polynomials and the Problem of Moments
- Convex Relaxations and Integrality Gaps
- Sum of Squares Lower Bounds from Pairwise Independence
- Lower Bounds on the Size of Semidefinite Programming Relaxations
- Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
- Theta Bodies for Polynomial Ideals
- Subexponential Algorithms for Unique Games and Related Problems
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy
- Class of global minimum bounds of polynomial functions
- On the Shannon capacity of a graph
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- CSP gaps and reductions in the lasserre hierarchy
- MaxMin allocation via degree lower-bounded arborescences
- Computation of the Lasserre Ranks of Some Polytopes
- Hypercontractivity, sum-of-squares proofs, and their applications
- Rounding Semidefinite Programming Hierarchies via Global Correlation
- Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- Expander flows, geometric embeddings and graph partitioning
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Complexity of Positivstellensatz proofs for the knapsack
- Complexity of Null- and Positivstellensatz proofs
