On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy
From MaRDI portal
Publication:3448844
DOI10.1007/978-3-662-47672-7_71zbMath1440.90043OpenAlexW2258079515MaRDI QIDQ3448844
Samuli Leppänen, Adam Kurpisz, Monaldo Mastrolilli
Publication date: 27 October 2015
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-662-47672-7_71
Related Items (6)
Sum-of-squares rank upper bounds for matching problems ⋮ A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem ⋮ Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators ⋮ An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem ⋮ Sum-of-squares hierarchy lower bounds for symmetric formulations ⋮ Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
- 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
- Analysis of Boolean Functions
- 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
- How to Sell Hyperedges: The Hypermatching Assignment Problem
- Approximability and proof complexity
- 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
This page was built for publication: On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy
