Sherali-Adams strikes back
From MaRDI portal
Recommendations
Cites work
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A nearly tight sum-of-squares lower bound for the planted clique problem
- An introduction to matrix concentration inequalities
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
- Counting Walks and Graph Homomorphisms via Markov Chains and Importance Sampling
- Geometry of cuts and metrics
- scientific article; zbMATH DE number 426360 (Why is no real title available?)
- scientific article; zbMATH DE number 510844 (Why is no real title available?)
- scientific article; zbMATH DE number 3417498 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Integrality gaps for Sherali-Adams relaxations
- Laplacian eigenvalues and the maximum cut problem
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Linear programming relaxations of \textsc{maxcut}
- Local global tradeoffs in metric embeddings
- Local versus global properties of metric spaces
- Max cut and the smallest eigenvalue
- On the cut polytope
- Optimal Construction of Edge-Disjoint Paths in Random Graphs
- Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
- Proving integrality gaps without knowing the linear program
- Recognizing More Unsatisfiable Random k-SAT Instances Efficiently
- Rounding Semidefinite Programming Hierarchies via Global Correlation
- Size biased couplings and the spectral gap for random regular graphs
- Spectral techniques applied to sparse random graphs
- Strongly refuting random CSPs below the spectral threshold
- Sum of squares lower bounds for refuting any CSP
- The expected relative error of the polyhedral approximation of the max- cut problem
- The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
- The RPR2 rounding technique for semidefinite programs
- The spectral gap of dense random regular graphs
- Towards strong nonapproximability results in the Lovász-Schrijver hierarchy
Cited in
(3)
This page was built for publication: Sherali-Adams strikes back
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5158503)