scientific article

DOI10.4086/toc.2012.v008a012zbMath1253.68141OpenAlexW2185716868MaRDI QIDQ2913812

Konstantinos Georgiou, Madhur Tulsiani, Siavosh Benabbas, Avner Magen

Publication date: 27 September 2012

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

Full work available at URL: https://doi.org/10.4086/toc.2012.v008a012

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

constraint satisfactionintegrality gapslinear programming hierarchiessemidefinite programming hierarchiespromising predicate

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (7)

Cryptographic hardness of random local functions. Survey ⋮ Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators ⋮ Rank bounds for a hierarchy of Lovász and Schrijver ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods ⋮ Unnamed Item ⋮ No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ ⋮ Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs

Cites Work

• An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems

This page was built for publication: