Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
From MaRDI portal
Recommendations
- Approximating coloring and maximum independent sets in 3-uniform hypergraphs
- SDP-based algorithms for maximum independent set problems on hypergraphs
- SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs
- Approximating independent sets in sparse graphs
- On linear and semidefinite programming relaxations for hypergraph matching
Cites work
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A PTAS for the minimization of polynomials of fixed degree over the simplex
- Approximate graph coloring by semidefinite programming
- Approximating coloring and maximum independent sets in 3-uniform hypergraphs
- Coloring -colorable graphs using relatively small palettes
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Expander flows, geometric embeddings and graph partitioning
- scientific article; zbMATH DE number 5485464 (Why is no real title available?)
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- scientific article; zbMATH DE number 1757962 (Why is no real title available?)
- scientific article; zbMATH DE number 2119703 (Why is no real title available?)
- scientific article; zbMATH DE number 3249395 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Integrality gaps for Sherali-Adams relaxations
- Integrality gaps of 2-o(1) for vertex cover SDPs in the Lovász-Schrijver hierarchy
- Linear programming relaxations of \textsc{maxcut}
- Near-optimal algorithms for unique games
- New approximation guarantee for chromatic number
- On the complexity of Putinar's Positivstellensatz
- On the power of unique 2-prover 1-round games
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Proving integrality gaps without knowing the linear program
- Some optimal inapproximability results
- The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
- Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy
Cited in
(19)- Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators
- Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
- Optimization and operations research in mitigation of a pandemic
- Integrality gaps for colorful matchings
- A comprehensive analysis of polyhedral lift-and-project methods
- Convex relaxations and integrality gaps
- Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
- On the hardest problem formulations for the 0/1 Lasserre hierarchy
- Integrality gaps of linear and semi-definite programming relaxations for knapsack
- On the hardest problem formulations for the 0/1 Lasserre hierarchy
- A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies
- scientific article; zbMATH DE number 7378399 (Why is no real title available?)
- Sum-of-squares bounds via Boolean function analysis
- Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph
- A logarithmic approximation of linearly-ordered colourings
- Linearly ordered colourings of hypergraphs
- Application of the level-2 quantum Lasserre hierarchy in quantum approximation algorithms
- Wireless capacity with arbitrary gain matrix
- Independent sets in semi-random hypergraphs
This page was built for publication: Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3541786)
