Extending SDP integrality gaps to Sherali-Adams with applications to quadratic programming and MaxCutGain

DOI10.1007/978-3-642-13036-6_23zbMATH Open1285.90028OpenAlexW1585955818MaRDI QIDQ3569826FDOQ3569826

Authors: Siavosh Benabbas, Avner Magen 

Publication date: 22 June 2010

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-13036-6_23

Recommendations

• Integrality gaps for Sherali-Adams relaxations
• Tight gaps for vertex cover in the Sherali-Adams SDP hierarchy
• Linear programming relaxations of \textsc{maxcut}
• SDP gaps and UGC-hardness for max-cut-gain
• CSP gaps and reductions in the lasserre hierarchy

Mathematics Subject Classification ID

Quadratic programming (90C20) Semidefinite programming (90C22) Integer programming (90C10)

Cited In (10)

• A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
• Exponential lower bounds for polytopes in combinatorial optimization
• Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
• Integrality gaps of linear and semi-definite programming relaxations for knapsack
• Integrality gaps for Sherali-Adams relaxations
• Superlinear Integrality Gaps for the Minimum Majority Problem
• Uncapacitated flow-based extended formulations
• A bounded degree SOS hierarchy for polynomial optimization
• Linear programming relaxations of \textsc{maxcut}
• A comprehensive analysis of polyhedral lift-and-project methods

This page was built for publication: Extending SDP integrality gaps to Sherali-Adams with applications to quadratic programming and MaxCutGain

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3569826)