Sherali-Adams strikes back

DOI10.4086/TOC.2021.V017A009MaRDI QIDQ5158503zbMATH OpenOpenAlexFDO

Authors Ryan O'Donnell, Tselil Schramm

Publication date 25 October 2021

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1812.09967

zbMATH Keywords

combinatorial optimizationhierarchiesSherali-Adams

Mathematics Subject Classification ID

Complexity of proofs (03F20) Theory of computing (68Qxx) Approximation algorithms (68W25)

Recommendations

• Sherali-adams strikes back
• Integrality gaps for Sherali-Adams relaxations
• Linear programming relaxations of \textsc{maxcut}
• Stronger linear programming relaxations of max-cut
• On the optimality of the random hyperplane rounding technique for MAX CUT

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)

• Sherali-adams strikes back
• Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
• A 7 / 3-approximation algorithm for feedback vertex set in tournaments via Sherali-Adams

Describes a project that uses

Uses Software

• Outward rotations

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)