Improved Approximation Guarantees through Higher Levels of SDP Hierarchies

DOI10.1007/978-3-540-85363-3_5zbMath1159.68664OpenAlexW1593162480MaRDI QIDQ3541786

Eden Chlamtáč, Gyanit Singh

Publication date: 27 November 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85363-3_5

Mathematics Subject Classification ID

Semidefinite programming (90C22) Hypergraphs (05C65) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (15)

Independent sets in semi-random hypergraphs ⋮ On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy ⋮ Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials ⋮ Optimization and operations research in mitigation of a pandemic ⋮ Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators ⋮ Integrality gaps for colorful matchings ⋮ Unnamed Item ⋮ On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy ⋮ Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack ⋮ Unnamed Item ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods ⋮ Convex Relaxations and Integrality Gaps ⋮ Wireless capacity with arbitrary gain matrix ⋮ A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of Putinar's Positivstellensatz
• A PTAS for the minimization of polynomials of fixed degree over the simplex
• Approximating Coloring and Maximum Independent Sets in 3-Uniform Hypergraphs
• Near-optimal algorithms for unique games
• New approximation guarantee for chromatic number
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• On the power of unique 2-prover 1-round games
• Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy
• Approximate graph coloring by semidefinite programming
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
• Coloring -colorable graphs using relatively small palettes
• Integrality gaps for Sherali-Adams relaxations
• Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the Lovász–Schrijver Hierarchy
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• Expander flows, geometric embeddings and graph partitioning

This page was built for publication: Improved Approximation Guarantees through Higher Levels of SDP Hierarchies