Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy

DOI10.1145/1060590.1060634zbMath1192.90123OpenAlexW2059187303MaRDI QIDQ3581430

Iannis Tourlakis, Michael Alekhnovich

Publication date: 16 August 2010

Published in: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1060590.1060634

Mathematics Subject Classification ID

Boolean programming (90C09) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines ⋮ Improved Approximation Guarantees through Higher Levels of SDP Hierarchies ⋮ Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack ⋮ Convex Relaxations and Integrality Gaps ⋮ Lift-and-project methods for set cover and knapsack ⋮ Semidefinite and linear programming integrality gaps for scheduling identical machines ⋮ Tight rank lower bounds for the Sherali-Adams proof system ⋮ Superlinear Integrality Gaps for the Minimum Majority Problem

This page was built for publication: Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy