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

DOI10.1007/978-3-642-13036-6_23MaRDI QIDQ3569826zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

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
• Uncapacitated flow-based extended formulations
• Superlinear Integrality Gaps for the Minimum Majority Problem
• 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)